Heap Sort (힙 정렬)

힙 정렬은 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법으로, 내림차순 정렬을 위해서는 최대 힙을 구성하고, 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

힙 정렬은 아래와 같은 방식으로 동작한다.

1. n개의 노드에 대한 완전 이진 트리를 구성한다.  2. 최대(최소) 힙을 구성한다.  3. 가장 큰(작은) 수를 가장 작은(큰) 수와 교환한다.  4. 2와 3을 반복한다.

완전 이진 트리를 구성하는 예를 아래 그림과 같다.

구현된 Class는 아래와 같다.

class HeapSort { public static void heapSort(int[] arr) { int heapSize = arr.Length; ​ for (int i = (heapSize - 1) / 2; i >= 0; i--) { maxHeapify(arr, heapSize, i); } ​ for (int j = heapSize - 1; j > 0; j--) { int temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; ​ heapSize--; ​ maxHeapify(arr, heapSize, 0); } } ​ private static void maxHeapify(int[] arr, int heapSize, int index) { int leftChild = index * 2 + 1; int rightChild = index * 2 + 2; int largest = 0; ​ if (leftChild < heapSize && arr[leftChild] > arr[index]) { largest = leftChild; } else { largest = index; } ​ if (rightChild < heapSize && arr[rightChild] > arr[largest]) { largest = rightChild; } ​ if (largest != index) { int temp = arr[index]; arr[index] = arr[largest]; arr[largest] = temp; ​ maxHeapify(arr, heapSize, largest); } } }

시간복잡도는 O(nlogn) 이다.

참조 1 : https://ko.wikipedia.org/wiki/힙_정렬

참조 2 : http://geeksquiz.com/heap-sort/