#13. 힙 정렬(Heap Sort)

힙 정렬(Heap Sort)

• 힙 트리(트리구조에서 자식노드보다 부모노드가 큰 상태)를 이용해서 정렬하는 방법
• 힙(Heap) : 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 완전이진트리
• 완전이진트리(Complete binary tree) : 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨
• 시간복잡도 : O(n log n)
• 임시 저장을 위한 메모리 사용이 필요 없어서 병합 정렬의 단점을 보완한 정렬방법
• 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법 (내림차순 정렬 : 최대 힙 구성 / 오름차순 정렬 : 최소 힙 구성)

---

알고리즘

 

1. n개의 노드에 대한 완전 이진트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다.
2. 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
4. 2와 3을 반복한다.

---

최대 힙(Max Heaps)

• 부모가 자식 노드의 값보다 더 큰 노드 값들로 구성된 트리

 

최소 힙(Min Heaps)

• 부모가 자식 노드의 값보다 더 작은 노드 값들로 구성된 트리

---

관련 함수

upHeap 함수

• 아래에서 위로 올라가면서 자리를 바꾸는 함수

void upHeap(int array[], int k) {
	int v;
	v = array[k];
	array[0] = MAX;
	while (array[k / 2] <= v) // 부모 <= 자식
	{
		array[k] = array[k / 2];
		k /= 2;
	}
	array[k] = v;
}

 

 

downHeap 함수

• 위에서 아래로 내려가면서 비교하는 함수
• 자식노드 왼쪽과 오른쪽 노드를 비교해서 더 큰 노드를 이용

void downHeap(int array[], int n, int k) {
	int i;
	int v = array[k];

	while (k <= n / 2) {
		i = k << 1; // 2*k
		if (i<n && array[i]<array[i + 1]) 
			i++; //왼쪽, 오른쪽 노드 비교
		if (v >= array[i]) 
			break;
		array[k] = array[i];
		k = i;
	}
	array[k] = v;
}

 

void downheap(int cur, int k)
{
  int left, right, p;
    while(cur < k) {
      left = cur * 2 + 1;
      right = cur * 2 + 2;

      if (left >= k && right >= k) break;

      p = cur;
      if (left < k && data[p] < data[left]) {
        p = left;
      }
      if (right < k && data[p] < data[right]) {
        p = right;
      }
      if (p == cur) break;

      swap(&data[cur],&data[p]);
      cur=p;
    }
}

 

 

heapify 함수

• 힙(heap) 상태를 만드는 함수

//heapify, 힙 상태 만들기 
void heapify(int *arr, int size) {
	for (int i = 1; i<size; ++i) {
		int child = i;
		do {
			//자식 노드가 부모 노드보다 크면 교환
			int root = (child - 1) / 2;
			if (arr[root]<arr[child]) {
				int temp = arr[root];
				arr[root] = arr[child];
				arr[child] = temp;
			}
			child = root;
		} while (child != 0);	//최상단 노드까지 점검
	}
}

 

void heapify(int n)
{
  int i,p;
  for(i = (n-1)/2; i >= 0; i--){
    downheap(i,n);
  }
  //for(i=0;i<size;++i)printf("%d ",data[i]);
  //printf("\n");
}

 

 

heap 함수

void heap()
{
  int k;
  heapify(size);
  for(k = size-1; k > 0; ){
    swap(&data[0],&data[k]);
    //k--;
    downheap(0,k);
    k--;
  }
}

 

 

insert 함수

• 입력받은 배열을 트리구조로 사용하기 위해 입력하는 함수

void insert(int array[], int *hn, int v) {
	array[++(*hn)] = v;
	upHeap(array, *hn);
}

 

delete 함수

• 정렬된 데이터를 받아오는 함수

int delete(int array[], int *n) {
	int v = array[1];
	array[1] = array[(*n)--];
	downHeap(array, *n, 1);
	return v;
}

 

---

References

 

ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC

힙 정렬 - 위키백과, 우리 모두의 백과사전

parkdream.tistory.com/116

[C] 힙 정렬(Heap Sort)

gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

[알고리즘] 힙 정렬(heap sort)이란 - Heee's Development Blog

swblossom.tistory.com/45

[C/C++] 힙 정렬(heap sort)로 오름차순 정렬하기