[힙 정렬] 힙 자료구조를 활용한 제자리 정렬 알고리즘

Dachaes 2025. 5. 7. 21:09

728x90

힙 정렬(Heap Sort)

힙 정렬(Heap Sort)은 완전 이진 트리 기반의 힙(Heap) 자료구조를 활용하는 정렬 알고리즘입니다. 정렬 과정에서 힙을 사용해 가장 큰 값(또는 가장 작은 값)을 빠르게 추출하고, 이를 반복하여 정렬을 완성합니다.

힙 정렬은 시간 복잡도가 항상 O(n log n)으로 일정하며, 추가적인 메모리를 거의 사용하지 않는 제자리(in-place) 정렬입니다. 단점은 안정 정렬이 아니며, 구현이 다소 복잡하다는 점이지만, 일정한 성능과 메모리 효율이 요구되는 상황에서는 매우 유용한 선택이 될 수 있습니다.

1. 힙 정렬이란?

힙 정렬은 다음과 같은 두 단계를 반복합니다.

최대 힙(Max Heap)을 구성하여 가장 큰 값을 루트로 보냅니다.
가장 큰 값을 배열 뒤로 보내고, 남은 요소로 다시 힙을 재정렬합니다.

작동 방식 (오름차순 정렬 기준)

배열을 최대 힙(Max Heap) 구조로 만듭니다.
루트(가장 큰 값)를 끝으로 보내고, 마지막 요소와 교환합니다.
남은 힙 크기를 줄이고 다시 힙 정렬(heapify) 수행합니다.
이 과정을 반복하면, 전체 배열이 오름차순으로 정렬됩니다.

장점

최악의 경우에도 O(n log n) 성능 보장
추가 메모리 없이 정렬 가능
데이터가 클수록 안정적인 성능 발휘

단점

안정 정렬이 아님
힙 자료구조에 대한 이해 필요
구현 복잡도 ↑ (퀵 정렬보다 어려움)

2. 예시

초기 배열 : [4, 10, 3, 5, 1]

최대 힙 구성 : [10, 5, 3, 4, 1]
10과 마지막 값 1 교환 → [1, 5, 3, 4, 10]
1 이하 재정렬 → [5, 4, 3, 1, 10]
반복 → 최종 : [1, 3, 4, 5, 10]

3. 언어별 구현 예제

a. Python

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # 최대 힙 구성
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 힙에서 하나씩 추출
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

b. C++

void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;

    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();

    // 힙 구성
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 하나씩 힙에서 꺼냄
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

c. Java

void heapify(int[] arr, int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;

    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

void heapSort(int[] arr) {
    int n = arr.length;

    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i >= 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

d. JavaScript

function heapify(arr, n, i) {
  let largest = i;
  const l = 2 * i + 1;
  const r = 2 * i + 2;

  if (l < n && arr[l] > arr[largest]) largest = l;
  if (r < n && arr[r] > arr[largest]) largest = r;

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

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);
  }
}

4. 시간 복잡도 분석

케이스	시간 복잡도
최선	O(n log n)
평균	O(n log n)
최악	O(n log n)
공간 복잡도	O(1)
정렬 안정성	불안정 정렬

힙 구성 : O(n)
힙에서 n번 추출 × O(log n) → O(n log n)
추가 메모리 없이 in-place로 동작 (배열 자체를 이용)

5. 마무리

힙 정렬은 힙 자료구조를 이용해 정렬하는 알고리즘으로, 항상 일정한 시간 복잡도를 보장합니다.
추가 공간이 거의 필요 없는 제자리 정렬이며, 대용량 데이터에서 메모리 효율이 중요할 때 유리합니다.
다만 안정 정렬이 아니며, 삽입 정렬처럼 특정 상황에서 빠른 알고리즘은 아닙니다.
힙 자료구조와 정렬 로직이 함께 필요한 문제(예: 우선순위 큐 문제)에서도 자주 활용됩니다.