데이터 쌓 기 구조 와 쌓 기 정렬 에 대한 개인 적 이해

쌓 기 순위 에 대해 일주일 동안 연 구 했 습 니 다. 인터넷 포럼 CSDN 이나 도서관 서적 에서 모두 많은 이익 을 얻 었 지만 지식 내용 은 많 지 않 습 니 다. 어떻게 이해 하 는 지 는 자신의 것 입 니 다.여기 서 나 는 스스로 정렬 하 는 인식 을 써 보 겠 다.
먼저 명확 하 게 해 야 할 관점 은:
1. 더 미 는 일종 의 데이터 구조 이다.
일반적으로 데이터 구조 에 필요 한 작업 은 세 가지 가 있 습 니 다. 초기 화, 데이터 삽입, 데이터 삭제.쌓 아 올 리 는 것 도 예 외 는 아니다.따라서 우리 가 데이터 구조의 기본 적 인 조작 을 쓰 면 우 리 는 그것 을 포장 하여 다른 곳 에 사용 할 수 있다.예 를 들 어 이런 데이터 구 조 를 쌓 아서 다른 정렬 작업 을 할 수 있다.상승 은 아버지의 노드 만 보고, 하락 은 아들 만 본다.
2. 본 논문 에 쌓 인 저장 소 는 순서 배열 을 바탕 으로 한다.
배열 의 실현 은 체인 이나 순서 일 수 있 기 때문에 여기 서 실 현 될 때 일반적인 상황 이 고 순서 배열 을 바탕 으로 순서 배열 로 쌓 인 내용 을 저장 하 는 것 이다.
그 중에서 사용 할 두 요 소 를 교환 하 는 작은 함수:
 

void exchange(int *a,int *b)

{

	int temp=*a;

	*a=*b;

	*b=temp;

}

 
 
데이터 구조 중의:
삽입 방법:
우리 가 삽입 방법 을 생각 할 때마다 쌓 인 데 이 터 는 배열 의 마지막 요소 에서 삽입 된다.따라서 매번 에 하나의 요 소 를 삽입 한 후에 이 배열 은 한 무더기 의 조건 을 만족 시 키 지 않 기 때문에 더 미 를 회복 해 야 한다. 기본 적 인 사상 은 삽 입 된 값 a [i] 를 그의 아버지 와 비교 한 다음 에 이들 의 값 을 교환 할 지 여 부 를 결정 하고 계속 순환 하 는 것 이다. 쌓 아 올 릴 때 까지 직관 적 으로 보면 새로 삽 입 된 요소 이 고 쌓 아 올 리 는 과정 이다.

 
  
//      

void MinHeapFixUp(int a[],int i)//       ，    

{

	int j;

	j=(i-1)/2;

	while(j>=0&&i!=0)

	{

		if (a[j]<a[i]) break;

		exchange(&a[i],&a[j]);

		i=j;

		j=(i-1)/2;

	}

}
  
  
void MinHeapAddNumber(int a[],int n,int nNum)//               

{

	a[n]=nNum;

	MinHeapFixUp(a,n);

}
  
  
삭제 방법:
더미 의 정의 에 따라 더미 에 서 는 매번 0 번 째 데이터 만 삭제 할 수 있다.따라서 복 구 를 편리 하 게 하기 위해 실제 작업 은 마지막 데이터 의 값 을 루트 의 결점 에 부여 한 다음 에 루트 의 결점 부터 위 에서 아래로 조정 하 는 것 이다.조정 할 때 현재 좌우 아들 중에서 가장 작은 것 을 찾 고 있다. 만약 에 아버지 가 이것 보다 더 작은 것 을 맺 으 면 조정 할 필요 가 없다 는 것 이다.반면 둘 을 바 꿔 아버 지 를 계속 생각 했다.그 과정 은 뿌리 결점 에서 데 이 터 를 가 라 앉 히 는 과정 과 같다.
  
/     :      i   ，                 ，        

//   i     i    ，   i            ,n         

void MinHeapFixdown(int a[],int i,int n)

{

	

	int left=2*i+1;

	int right=left+1;

	int small=left;

	while(left<n)//              ，     

	{

		//         

		if(right<n)

		{

			if (a[left]<=a[right])

			{

				small=left;

			}

			else small=right;

			if (a[small]<a[i])

			{

				exchange(&a[small],&a[i]);

			}

			else break;

		}

		else

		{

			small=left;

			if (a[small]<a[i])

			{

				exchange(&a[small],&a[i]);

			}

			else break;

		}

		i=small;

		left=2*i+1;

		right=left+1;

	}

}
  
  
 
  
void MinHeapDeleteNumber(int a[],int n)

{

	exchange(&a[0],&a[n-1]);

	MinHeapFixdown(a,0,n-1);

}
  
  
 초기 화:
초기 화 는 두 가지 최소 더 미 를 만 드 는 방법 이 있 습 니 다. 하 나 는 Fixdown 을 이용 하 는 것 이 고 다른 하 나 는 Fixup 를 이용 하 는 것 입 니 다.
void MakeMinHeap1(int a[], int n)  

{  

	for (int i = n/2-1; i >= 0; i--)  

	MinHeapFixdown(a, i, n);

}

  
  
void MakeMinHeap2(int a[],int n)

{

	for (int i=0;i<n;i++)

	{

		MinHeapFixUp(a,i);

	}

}
  
마지막: 쌓 기 라 는 데이터 구 조 를 이용 하여 쌓 기 정렬 을 실현 합 니 다.
  
void MinheapsortTodescendarray(int a[], int n)  

{  

	for (int i = n; i >=1 ; i--)  

	{  

		MinHeapDeleteNumber(a,i);

	}  

}
  
void main()

{

	int arr[]={0,1,5,4,2,7,6,8};

	//MakeMinHeap1(arr,8);

	MinheapsortTodescendarray(arr,8);

	for (int i=0;i<8;i++)

	{

		printf("%d ",arr[i]);

	}

	printf("
");

	

	MakeMinHeap1(arr,8);

	for (int i=0;i<8;i++)

	{

		printf("%d ",arr[i]);

	}

	printf("
");

        MakeMinHeap2(arr,8);

	for (int i=0;i<8;i++)

	{

		printf("%d ",arr[i]);

	}

	printf("
");



}