힙 정렬

배열을 Heap으로 만든 뒤, 루트(최댓값)를 꺼내 배열 끝에 배치하며 정렬하는 알고리즘입니다.

동작 과정

[5, 3, 8, 1, 2]

1. Max Heap 구성 (heapify):
   [8, 3, 5, 1, 2]

2. 루트(최댓값)를 끝으로 보내고 힙 재구성 반복:
   8↔2 → [2, 3, 5, 1, | 8] → heapify → [5, 3, 2, 1, | 8]
   5↔1 → [1, 3, 2, | 5, 8] → heapify → [3, 1, 2, | 5, 8]
   3↔2 → [2, 1, | 3, 5, 8] → heapify → [2, 1, | 3, 5, 8]
   2↔1 → [1, | 2, 3, 5, 8]

결과: [1, 2, 3, 5, 8]

구현

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

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

    // 루트를 끝으로 보내며 정렬
    for (int i = n - 1; i > 0; i--) {
        int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp;
        heapify(arr, i, 0);
    }
}

void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1, right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest])   largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
        int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp;
        heapify(arr, n, largest);
    }
}

복잡도

• 불안정 정렬 X
• in-place O
• 추가 메모리 없이 O(n log n) 보장 → 메모리 제약 환경에 유리

→ 정렬