힙 자료구조에 대한 정리

‣

힙 정렬 설계(Heap Sort)

힙 정렬에서는 배열을 힙 구조로 재구성하는 makeheap()연산이 필요합니당

개선된 힙 생성 연산 MakeHeap 설계

미리 n개 레코드가 모두 주어진 경우에만 가능합니다.

heap구현시 하나씩 삽입하면서 매번 Upheap연산을 수행해 주었다. 그것을 개선

루트부터 heap을 만들어가는 것이 아닌 leaf 노드부터 이미 heap들이 형성되어있다고 가정해 거꾸로 부모노드들을 붙여나가는 방식

1. 주어진 배열을 일단 heap으로 가정

   

2. 60, 20, 70, 80 은 자식노드가 없으므로 독립적인 maxheap으로 볼 수 있다.

   

   

3. 이제 그 위에 50까지를 보면, 인덱스에 의해 50이 부모노드, 70, 80이 자식노드가 되는데, 그럼 이제 60과 20은 여전히 독립적인 maxheap이고 50, 70, 80으로 이뤄진 heap은 힙 조정을 통해 80을 부모노드로 옮기고 70과 50을 자식노드로 갖도록 한다.

   

   

4. 이제 10까지를 보면,

   

   10, 60, 20으로 이뤄진 힙, 80, 70, 50으로 이뤄진 힙 두개로 볼 수 있다.

   10, 60, 20으로 이뤄진 힙 재조정

   

   

5. 마지막으로 루트인 30까지 보고 힙조정을 다시 해주면

   

   

   이렇게 완성!

힙정렬 구현

void MakeHeap(int A[], int Root, int LastNode)
{
	int Parent, LeftSon, Son, RootValue;
	Parent = Root;
	RootValue = A[Root];
	LeftSon = 2 * Parent + 1;
	RightSon = LeftSon + 1;
	while LeftSon <= LastNode {
		if(RightSon <= LastNode && A[LeftSon] < A[RightSon])
			Son = RightSon;
		else Son = LeftSon; // LeftSon이랑 RightSon 중 키값이 더 큰 것을 Son에 저장
		if (RootValue < A[Son]){ 
			A[Parent] = A[Son]; // A[Son]이 RootValue보다 크면 A[Parent]와 A[son]을 바꾼다.(힙조정)
			Parent = Son; // 이후에는 Parent 인덱스를 Son의 인덱스로 바꾸고
			LeftSon = Parent * 2 + 1; // LeftSon과 RightSon 값도 다시 바꿔주고 아무튼 재조정하는 과정
			RightSon = LeftSon + 1;}
		else break;// A[Son]보다 RootValue가 크다면 조정할 필요가 없으므로 break
	A[Parent] = RootValue;
}

#define Swap(int &a, int &b) \\
{\\
int temp;\\
temp = a;\\
a = b;\\
b = temp;\\
}
void HeapSort(int A[], int n)
{/* 입력: A[0:n-1], n : 정렬할 원소 개수
		출력: A[0:n-1] : 정렬된 배열 */
	int i;
	for(i=n/2;i>=0;i--)
		MakeHeap(A, i, n－1);
	for (i ＝ n－1; i ＞ 0; i－－){
		Swap(&A[0], &A[i]);
		MakeHeap(A, 0, i－1); }
}