Heap Sort

heap sort, heapsort, 힙 정렬, Heapsort

정의

Heap Sort (힙 정렬) 는 힙 (heap) 자료구조의 최댓값 / 최솟값을 O(log n) 에 추출 하는 성질을 이용한 정렬. In-place 이고 최악 O(n log n) 을 보장.

J.W.J. Williams 가 1964 년 고안. Quicksort 만큼 빠르지는 않지만 응답 시간이 일정하고 메모리 효율이 좋다. LIMIT N 같은 Top-K 문제 에 가장 적합. C++ std::sort (Introsort) 의 폴백 알고리즘.

전체 비교는 정렬 알고리즘 참고.

시각화

알고리즘

heapSort(arr):
  buildMaxHeap(arr)               // 1단계: 힙 구성
  for i = n-1 down to 1:
    swap(arr[0], arr[i])          // 2단계: 최댓값을 끝으로
    heapifyDown(arr, 0, i)        // 새 root 를 내려보내 힙 유지

buildMaxHeap(arr):
  for i = n/2 - 1 down to 0:
    heapifyDown(arr, i, n)

heapifyDown(arr, i, size):
  largest = i
  l = 2i + 1
  r = 2i + 2
  if l < size and arr[l] > arr[largest]: largest = l
  if r < size and arr[r] > arr[largest]: largest = r
  if largest != i:
    swap(arr[i], arr[largest])
    heapifyDown(arr, largest, size)

두 단계로 나뉜다

1. 힙 빌드 (Build Max Heap): 배열을 max-heap 으로 만든다. O(n).
2. 추출 반복 (Extract Max): 루트 (최댓값) 를 배열 끝으로 보내고, 힙 크기를 1 줄인 뒤 heapify. n 번 반복 → O(n log n).

배열로 힙 표현

힙은 별도 트리 구조 없이 배열만으로 표현. 인덱스 i 일 때:

• 부모: (i - 1) / 2
• 왼쪽 자식: 2i + 1
• 오른쪽 자식: 2i + 2

배열: [9, 7, 8, 3, 5, 6, 4, 1, 2]
트리:        9
           /   \
         7      8
        / \    / \
       3   5  6   4
      / \
     1   2

복잡도

항목	값
시간 (최선)	O(n log n)
시간 (평균)	O(n log n)
시간 (최악)	O(n log n)
공간	O(1)
안정성	✗ Unstable
In-place	✓

왜 buildMaxHeap 이 O(n) 인가

힙 빌드: 리프부터 거꾸로 heapify
- 리프 (n/2 개): heapify 0 회
- 부모 노드 (n/4 개): heapify 1 회
- ... 
- 루트 (1 개): heapify log n 회

총 비용 = Σ (n / 2^(h+1)) × h ≤ 2n = O(n)

직관적으로는 O(n log n) 일 것 같지만, 대부분의 노드가 리프 근처라 heapify 비용이 작다.

Quicksort 와의 비교

항목	Heap Sort	Quick Sort
평균 시간	O(n log n)	O(n log n)
최악 시간	O(n log n) 보장	O(n²)
공간	O(1)	O(log n)
안정성	✗	✗
In-place	✓	✓
캐시 친화	△ (인덱스 점프)	✓
실측 속도	Quick 보다 2-3x 느림	빠름

Top-K (Partial Sort) 에 최적

전체 정렬이 아니라 상위 K 개만 필요하면 Heap 이 압도적이다.

전체 정렬: O(n log n)
Top-K via Heap: O(n log K)

K=10, n=10⁹ 라면 차이가 1000× 가까이 난다.

알고리즘

function topK(arr, k) {
  // 크기 K 의 min-heap 유지
  const heap = new MinHeap();
  for (const x of arr) {
    if (heap.size() < k) {
      heap.push(x);
    } else if (x > heap.peek()) {
      heap.pop();
      heap.push(x);
    }
  }
  return heap.toArray();
}

각 원소를 한 번씩 보면서 heap 의 최솟값과 비교. heap 크기가 K 로 일정.

RDBMS 의 LIMIT 최적화

SELECT * FROM events ORDER BY ts DESC LIMIT 100;

Oracle / PostgreSQL 모두 이런 쿼리에서 Heap Sort 로 자동 전환. 전체 정렬을 하지 않고 크기 100 의 heap 만 유지한다. 정렬·해시는 메모리가 부족하면 어디로 새는가, PGA, work_mem, Workspace Memory 글에서 “LIMIT N 최적화 시 Heapsort” 라는 한 줄이 이 메커니즘.

우선순위 큐의 자료구조

Heap 은 사실상 [Priority Queue] 의 표준 구현. Dijkstra, A*, K-way merge, scheduler 등 광범위하게 사용.

// JavaScript 에는 빌트인 heap 이 없어 직접 구현
class MinHeap {
  constructor() { this.heap = []; }
  push(x) { /* heapify up */ }
  pop() { /* swap root with last, heapify down */ }
  peek() { return this.heap[0]; }
}

Python heapq, Java PriorityQueue, C++ std::priority_queue 모두 heap 기반.

K-way Merge 와의 관계

External Merge Sort 의 K-way merge 단계에서 K 개의 head 중 최솟값을 찾는 데 heap 사용. K=1000 짜리 머지에서 O(log 1000) ≈ 10 회 비교 로 최솟값 결정.

External Merge Sort 의 머지 단계:
  for each output position:
    min = heap.pop()      // O(log K)
    write min
    heap.push(next from min's run)

함정

1. 안정성 없음

Selection Sort 와 비슷한 이유. heap 추출 시 같은 값의 순서가 보장되지 않음.

2. 캐시 친화성 낮음

배열 인덱스가 i → 2i → 4i → … 로 건너뛰기 때문에 cache miss 가 많다. 같은 O(n log n) 이라도 실측은 Quick / Merge 보다 2-3 배 느리다.

3. 단순 정렬에는 잘 안 쓰임

전체 정렬에서 Heap 을 선호할 일은 드물다. Top-K, Priority Queue, K-way Merge 에서 빛난다.

실무 활용

• C++ std::sort: Introsort 내부에서 폴백
• std::partial_sort, std::nth_element: Heap 기반
• OS 스케줄러: priority queue
• 그래프 알고리즘: Dijkstra, Prim’s MST
• DB Top-K: ORDER BY ... LIMIT N
• K-way Merge: 외부 정렬

참고

• 정렬 알고리즘
• Quick Sort
• Merge Sort
• Selection Sort
• External Merge Sort
• 정렬·해시는 메모리가 부족하면 어디로 새는가, PGA, work_mem, Workspace Memory
• J.W.J. Williams, “Algorithm 232: Heapsort” (CACM 1964)
• Knuth, TAOCP Vol. 3 §5.2.3