[Sort] 힙 정렬(Heap Sort)

[출처 : http://proneer.tistory.com/entry/Sort-힙-정렬Heap-Sort]

힙 정렬(Heap Sort)를 알기 전에 먼저 힙이라는 자료구조에 대해서 알아야 한다. 힙은 보통 히프라고 불린다. 메모리공간에서 동적메모리가 저장되는 공간인 힙과 비교하기 위해 여기서도 히프라는 용어를 사용하기로 한다.

히프는 여러 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조로서 완전이진트리의 형태이다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같은 완전 이진트리를 최대히프라고 하고, 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 같은 완전 이진트리를 최소히프라고 한다.

[그림 1] 최대 히프의 예

[그림 2] 최소 히프의 예

히프는 우선순위 큐를 구현하는 한 방법이다. 따라서, 히프에서 삭제, 삽입 연산이 일어나게 되면 재 구성이 되어 우선순위를 만족해야 한다. 우선 순위라는 것이 앞의 예에서는 숫자의 크기에 따라 다르게 나타날 것이다.

히프를 이용한 정렬은 최대 히프와 최소 히프 모두를 이용할 수 있다. 최대 히프에서 삭제시 가장 큰값이 삭제되게 된다. 이렇게 반환된 삭제 값들을 정해진 자료구조의 뒤에서부터 채우면 정렬이 되는 것이다. 최소 히프라면 자료구조의 앞에서부터 채우면 될 것이다.


다음을 통해 히프 정렬의 알고리즘을 파악할 수 있을 것이다.

히프 정렬의 복잡도는 O(n log n)가 된다. 히프 정렬은 트리구조를 이용하기 때문에 전체 높이가 O(log n)이다. 따라서, 하나의 요소를 히프에 삽입하거나 삭제할 때 히프를 재 구성하는 시간은 O(log n)만큼 걸린다. 요소의 개수가 n개 이므로 전체적으로 거리는 시간은 O(n log n)이 된다. 히프 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때이다.

다음은 히프정렬을 구현한 예이다.

# Type 1
void heapsort(int arr[], unsigned int N)
{
          unsigned int n = N, i = n/2, parent, child;
           int t;
 
           for (;;) { /* Loops until arr is sorted */
                      if (i > 0) { /* First stage - Sorting the heap */
                                 i--;           /* Save its index to i */
                                 t = arr[i];   /* Save parent value to t */
                      } else {     /* Second stage - Extracting elements in-place */
                                 n--;           /* Make the new heap smaller */
                                 if (n == 0) return; /* When the heap is empty, we are done */
                                 t = arr[n];   /* Save last value (it will be overwritten) */
                                 arr[n] = arr[0]; /* Save largest value at the end of arr */
                      }
 
                      parent = i; /* We will start pushing down t from parent */
                      child = i*2 + 1; /* parent's left child */
 
                      /* Shift operation - pushing the value of t down the heap */
                      while (child < n) {
                                 if (child + 1 < n  &&  arr[child + 1] > arr[child]) {
                                            child++; /* Choose the largest child */
                                 }
                                 if (arr[child] > t) { /* If any child is bigger than the parent */
                                            arr[parent] = arr[child]; /* Move the largest child up */
                                            parent = child; /* Move parent pointer to this child */
                                            child = parent*2 + 1; /* Find the next child */
                                 } else {
                                            break; /* t's place is found */
                                 }
                      }
                      arr[parent] = t; /* We save t in the heap */
           }
}

# Type 2
#define LOOP(A,B) for(i=A;i<B;i++)
//Convert any random array to heap array
void heapify ( int list[] , int newnode )
{
          int done=0, dad, temp;
          dad = ( newnode - 1 ) / 2;

          while( dad >= 0 && !done) {
                    if(list[newnode] > list[dad]) {
                               temp = list[newnode];
                               list[newnode]=list[dad];
                               list[dad]=temp;
                               newnode = dad;
                               dad = dad/2;
                     } else
                             done = 1;

          }
}

void heapsort ( int list[] , int last )
{
           int i,temp;
           while(last > 0 ) {
                   temp = list[0];
                   list[0]=list[last];
                   list[last]= temp;
                   LOOP(0,last)
                   heapify(list,i);
                   last--;
           }
}

Reference : http://www.programmersheaven.com/download/34394/0/ZipView.aspx
                 http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Heapsort