힙 정렬 (Heap Sort) 설명과 JavaScript 예제

힙 정렬은 완전 이진 트리의 일종인 '힙(Heap)' 자료구조를 활용한 정렬 알고리즘입니다. 선택 정렬과 유사하지만, 최대값 또는 최소값을 효율적으로 선택하기 위해 힙 구조를 사용합니다. 시간 복잡도가 항상 O(n log n)으로 일정하며, 추가 메모리 없이 정렬할 수 있는 장점이 있습니다.

---

1. 힙의 개념

• 최대 힙 (Max Heap): 부모 노드가 자식 노드보다 크거나 같음
• 최소 힙 (Min Heap): 부모 노드가 자식 노드보다 작거나 같음

힙 정렬에서는 일반적으로 최대 힙을 사용하여 가장 큰 값을 루트로 올리고 배열의 뒤로 보냅니다.

---

2. 동작 원리

1. 배열을 최대 힙 구조로 변환 (build max heap)
2. 힙의 루트(최대값)를 배열 끝으로 보냄
3. 힙 크기를 줄이고 다시 heapify 수행
4. 위 과정을 반복하여 정렬 완료

---

3. JavaScript 예제 - 오름차순 정렬

function heapSort(arr) {
  const n = arr.length;

  // 최대 힙 구성
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // 하나씩 루트 추출하여 정렬
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // 최대값을 끝으로
    heapify(arr, i, 0); // 줄어든 힙에 대해 heapify
  }

  return arr;
}

function heapify(arr, size, root) {
  let largest = root;
  const left = 2 * root + 1;
  const right = 2 * root + 2;

  if (left < size && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < size && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest !== root) {
    [arr[root], arr[largest]] = [arr[largest], arr[root]];
    heapify(arr, size, largest);
  }
}

console.log(heapSort([4, 10, 3, 5, 1])); // [1, 3, 4, 5, 10]

• heapify: 주어진 노드를 기준으로 최대 힙 조건을 만족하도록 재정렬
• heapSort: 전체 배열에 대해 최대 힙 생성 후, 루트를 정렬 영역으로 보내며 반복

---

4. 성능 분석

구분	시간 복잡도
최선의 경우	O(n log n)
평균	O(n log n)
최악의 경우	O(n log n)

• 공간 복잡도: O(1) (제자리 정렬)
• 안정 정렬이 아님: 동일한 값의 상대 순서가 바뀔 수 있음

---

5. 힙 정렬의 특징

• 항상 일정한 시간 복잡도 보장
• 추가 메모리 없이도 정렬 가능 (in-place)
• 안정 정렬이 아니라는 점에서 병합 정렬과는 차이 있음

---

마무리

힙 정렬은 대규모 데이터를 안정적으로 처리할 수 있는 알고리즘 중 하나입니다. 특히 메모리 사용을 최소화해야 하거나 최악의 경우에도 성능이 유지되어야 할 때 유용합니다.

자바스크립트에서 기본 제공되는 sort()는 힙 정렬이 아닌, 구현체에 따라 병합/퀵 기반이므로 필요에 따라 직접 구현해보는 것도 좋습니다.