힙정렬(Heap Sort)

개요

힙정렬을 하기 위해서는 '최대힙', '최소힙'의 개념을 알아야 한다. 최대힙은 '두 노드값은 그 부모의 값보다 클 수 없다'는 정의를 만족하는 힙이며, 최소힙은 그와 반대로 '두 노드값은 그 부모의 값보다 작을 수 없다'는 정의를 만족하는 힙이다. 즉, 최대힙에서는 최대값이 루트에 있으며, 최소힙에서는 최소값이 루트에 있다.
최대힙의 성질을 이용해 오름차순 정렬을 할 수 있으며, 최소힙의 성질을 이용해 내림차순 정렬을 할 수 있다. 둘 중 하나만 확실하게 알아놓으면 다른 하나는 반대되는 성질로 인해 쉽게 추론할 수 있으므로 '최대힙을 이용한 오름차순 정렬'만 공부하겠다.

최대힙을 이용한 오름차순 정렬

1. 우선 오름차순으로 정렬해야할 배열이 주어지면 그 배열을 최대힙으로 만든다(buildMaxHeap). 최대힙의 정의를 만족시키기 위해서는 자식이 있는 노드만을 대상으로 하면 되므로 (heapSize / 2)부터 1까지의 인덱스를 대상으로 maxHeapify함수를 호출한다.
2. maxHeapify는 최대힙의 성질을 가지도록 만들어주는 함수다. 자식 노드 중 부모 노드보다 큰 값이 있다면 최대힙의 성질을 위반한다. 그러므로 해당 자식 노드의 값과 부모 노드의 값을 바꾼다(두 개의 자식 노드 모두 보모 노드보다 크다면 더 큰 자식노드를 부모 노드와 바꾼다). 이로써 최대힙의 성질을 유지할 수 있다. 마지막으로 자식의 자리로 간 부모 노드가 또 최대힙의 성질을 위반할 수 있으므로 재귀적으로 maxHeapify를 호출한다.
3. 2까지 마쳤다면 루트에는 힙의 최대값이 들어가있다. 이 값을 힙의 마지막(배열의 마지막) 원소와 바꾼다. 그럼 배열에서 가장 큰 원소가 배열의 가장 오른쪽에 위치하게 된다. 이로써 한 원소의 위치를 확정지었으므로 heapSize를 1 줄여준다(heapSize를 줄여주지 않으면 maxHeapify를 호출할 때 가장 큰 값이 힙의 마지막에 있으므로 최대힙의 성질을 위반하는 것으로 여긴다). 그리고 새로운 루트로 인해 최대힙의 성질을 위반하지 않도록 maxHeapify를 호출해준다.
4. 3의 과정을 heapSize에서 2까지 반복하면 오름차순 정렬이 완성된다.

최대힙을 이용한 오름차순 정렬 소스코드

#include <stdio.h>
#include <algorithm>
using namespace std;  
int heapSize = 7;  
// 0번째에 위치한 0은 정렬의 대상이 아니다. 
// 0번째 인덱스는 left, right 노드를 가질 수 없기 때문에 아무런 숫자를 넣어 자리를 채운 것이다.  
int A[] = {0, 2, 1, 3, 4, 7, 6, 4};  
void maxHeapify(int *A, int i) {  
  int largest = i, left = i << 1, right = (i << 1) + 1;  
  if (left <= heapSize && A[left] > A[largest]) largest = left;  
  if (right <= heapSize && A[right] > A[largest]) largest = right;  
  if (largest != i) {  
    swap(A[largest], A[i]);  
    maxHeapify(A, largest);  
  }  
}  
void buildMaxHeap(int *A) {  
  for (int i = heapSize / 2; i > 0; i--) {  
    maxHeapify(A, i);  
  }  
}  
void heapSort(int *A) {  
  buildMaxHeap(A);  
  for (int i = heapSize; i > 1; i--) {  
    swap(A[1], A[i]);  
    heapSize--;  
    maxHeapify(A, 1);  
  }  
}  
int main() {  
  for (int i = 1; i < 8; i++) printf("%d ", A[i]); // 2 1 3 4 7 6 4   
  printf("\n");  
  heapSort(A);  
  for (int i = 1; i < 8; i++) printf("%d ", A[i]); // 1 2 3 4 4 6 7   
  return 0;
}  

최소힙을 이용한 내림차순 정렬 소스코드

#include <stdio.h>
#include <algorithm>
using namespace std;
int heapSize = 7;
int A[] = {0, 2, 1, 3, 4, 7, 6, 4};
void minHeapify(int *A, int i) {
  int smallest = i, left = i << 1, right = (i << 1) + 1;
  if (left <= heapSize && A[left] < A[smallest]) smallest = left;
  if (right <= heapSize && A[right] < A[smallest]) smallest = right;
  if (smallest != i) {
    swap(A[smallest], A[i]);
    minHeapify(A, smallest);
  }
}
void buildMinHeap(int *A) {
  for (int i = heapSize / 2; i > 0; i--) {
    minHeapify(A, i);
  }
}
void heapSort(int *A) {
  buildMinHeap(A);
  for (int i = heapSize; i > 1; i--) {
    swap(A[1], A[i]);
    heapSize--;
    minHeapify(A, 1);
  }
}
int main() {
  for (int i = 1; i < 8; i++) printf("%d ", A[i]); // 2 1 3 4 7 6 4 
  printf("\n");
  heapSort(A);
  for (int i = 1; i < 8; i++) printf("%d ", A[i]); // 7 6 4 4 3 2 1 
  return 0;
}