Heap Sort
마지막 업데이트
힙 정렬은 배열을 이진 힙으로 다룹니다. 먼저 max-heap을 구축하여 가장 큰 원소가 루트(인덱스 0)에 오도록 합니다. 그런 다음 루트를 정렬되지 않은 마지막 원소와 반복해서 교환하여 최댓값을 제자리에 고정하고, 새 루트를 아래로 내려보내(sift down) 힙 속성을 회복합니다. 위의 재생 버튼을 눌러 힙 구축과 추출 과정을 확인하세요.
힙 정렬은 병합 정렬과 마찬가지로 O(n log n) 시간을 보장하지만, 추가 공간을 O(1)만 사용하며 제자리(in-place)에서 정렬합니다. 안정적이지 않고 퀵 정렬보다 캐시 동작이 나쁜 경향이 있어, 보장된 상한과 일정한 메모리가 모두 중요할 때 자주 선택됩니다.
시간 및 공간 복잡도
| 경우 | 복잡도 | 비고 |
|---|---|---|
| 최선의 경우 | O(n log n) | 구축 + n회 추출 |
| 평균의 경우 | O(n log n) | 무작위 순서 |
| 최악의 경우 | O(n log n) | 보장됨 |
| 공간 | O(1) | 제자리 |
| 안정성 | 아니요 | sift-down이 동일한 원소의 순서를 바꿈 |
단계별 설명
| 단계 | 무슨 일이 일어나는가 |
|---|---|
| 1 | 배열로부터 max-heap을 구축한다(마지막 부모부터 아래로 내려보낸다). |
| 2 | 루트(최댓값)를 힙의 마지막 원소와 교환한다. |
| 3 | 힙을 하나 줄인다 - 그 마지막 자리는 이제 정렬 완료. |
| 4 | 새 루트를 아래로 내려보내 max-heap 속성을 회복한다. |
| 5 | 힙에 원소가 하나 남을 때까지 반복한다. |
예제 풀이
[3, 1, 6, 5, 2, 4] 정렬하기. 막대 |는 줄어드는 힙과 정렬된 꼬리 사이의 경계를 나타냅니다:
| 패스 | 배열 | 동작 |
|---|---|---|
| 힙 구축 | [6, 5, 4, 1, 2, 3] | 마지막 부모부터 아래로 내려보내 max-heap을 구축한다. 이제 6이 루트에 있다. |
| 1 | [5, 3, 4, 1, 2 | 6] | 루트 6을 마지막 자리와 교환하고, 힙을 줄인 뒤 3을 아래로 내려보낸다. |
| 2 | [4, 3, 2, 1 | 5, 6] | 루트 5를 꺼낸 뒤 2를 아래로 내려보내 4가 루트로 올라온다. |
| 3 | [3, 1, 2 | 4, 5, 6] | 루트 4를 꺼낸 뒤 1을 아래로 내려보내 3이 루트로 올라온다. |
| 4 | [2, 1 | 3, 4, 5, 6] | 루트 3을 꺼낸다. 2는 이미 힙 속성을 만족한다. |
| 5 | [1 | 2, 3, 4, 5, 6] | 루트 2를 꺼낸다. 원소가 하나 남으므로 배열이 정렬 완료된다. |
힙 정렬을 사용할 때
| 사용할 때 | 피할 때 |
|---|---|
O(n²) 위험 없이 보장된 O(n log n) 최악의 경우가 필요할 때. | 동일한 키의 순서를 보존하는 안정 정렬이 필요할 때. |
메모리가 빠듯할 때 - 추가 공간을 O(1)만 쓰며 제자리에서 정렬한다. | 캐시 성능이 중요하고 데이터가 메모리에 들어갈 때 - 퀵 정렬이 대개 더 빠르다. |
| 이미 데이터 위에 힙(예: 우선순위 큐)을 유지하고 있을 때. | 비교 횟수를 최소로 하고 싶을 때 - 병합 정렬과 퀵 정렬이 실제로는 더 적게 비교하는 경우가 많다. |
| 신뢰할 수 없는 입력이 퀵 정렬의 최악의 경우를 유발할 수 있고 무작위화할 수 없을 때. | 데이터가 거의 정렬되어 있을 때 - 삽입 정렬이 그 위에서 거의 선형 시간으로 동작한다. |
Heap Sort 코드
Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Heap Sort 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.
Python로 구현한 Heap Sort 코드
Python
1def heap_sort(a):2 n = len(a)3 # Build a max-heap, deepest parent first4 for i in range(n // 2 - 1, -1, -1):5 sift_down(a, i, n)6 # Repeatedly move the max to the end and shrink the heap7 for end in range(n - 1, 0, -1):8 a[0], a[end] = a[end], a[0]9 sift_down(a, 0, end)10 return a11
12
13def sift_down(a, i, size):14 while True:15 largest = i16 left, right = 2 * i + 1, 2 * i + 217 if left < size and a[left] > a[largest]:18 largest = left19 if right < size and a[right] > a[largest]:20 largest = right21 if largest == i:22 return23 a[i], a[largest] = a[largest], a[i]24 i = largest25
26
27nums = [12, 11, 13, 5, 6, 7]28print("Before:", nums)29heap_sort(nums)30print("After: ", nums)JavaScript로 구현한 Heap Sort 코드
JavaScript
1function heapSort(a) {2 const n = a.length;3 // Build a max-heap, then repeatedly move the max to the end4 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n);5 for (let end = n - 1; end > 0; end--) {6 [a[0], a[end]] = [a[end], a[0]];7 siftDown(a, 0, end);8 }9 return a;10}11
12function siftDown(a, i, size) {13 while (true) {14 const left = 2 * i + 1;15 const right = 2 * i + 2;16 let largest = i;17 if (left < size && a[left] > a[largest]) largest = left;18 if (right < size && a[right] > a[largest]) largest = right;19 if (largest === i) return;20 [a[i], a[largest]] = [a[largest], a[i]];21 i = largest;22 }23}24
25const data = [5, 2, 9, 1, 7, 3];26console.log("Before:", data);27console.log("Sorted:", heapSort([...data]));Java로 구현한 Heap Sort 코드
Java
1import java.util.Arrays;2
3public class Main {4 static void heapSort(int[] arr) {5 int n = arr.length;6 // Build a max-heap, deepest parent first7 for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, i, n);8 // Repeatedly move the max to the end and shrink the heap9 for (int end = n - 1; end > 0; end--) {10 swap(arr, 0, end);11 siftDown(arr, 0, end);12 }13 }14
15 static void siftDown(int[] arr, int i, int size) {16 while (true) {17 int largest = i, l = 2 * i + 1, r = 2 * i + 2;18 if (l < size && arr[l] > arr[largest]) largest = l;19 if (r < size && arr[r] > arr[largest]) largest = r;20 if (largest == i) return;21 swap(arr, i, largest);22 i = largest;23 }24 }25
26 static void swap(int[] arr, int a, int b) {27 int tmp = arr[a];28 arr[a] = arr[b];29 arr[b] = tmp;30 }31
32 public static void main(String[] args) {33 int[] arr = {12, 11, 13, 5, 6, 7};34 System.out.println("Before: " + Arrays.toString(arr));35 heapSort(arr);36 System.out.println("After: " + Arrays.toString(arr));37 }38}C++로 구현한 Heap Sort 코드
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void siftDown(std::vector<int>& a, int n, int i) {11 while (true) {12 int largest = i, l = 2 * i + 1, r = 2 * i + 2;13 if (l < n && a[l] > a[largest]) largest = l;14 if (r < n && a[r] > a[largest]) largest = r;15 if (largest == i) return;16 std::swap(a[i], a[largest]);17 i = largest;18 }19}20
21void heapSort(std::vector<int>& a) {22 int n = static_cast<int>(a.size());23 // Build a max-heap in place24 for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, n, i);25 // Repeatedly move the max to the end and shrink the heap26 for (int end = n - 1; end > 0; --end) {27 std::swap(a[0], a[end]);28 siftDown(a, end, 0);29 }30}31
32int main() {33 std::vector<int> data = {12, 11, 13, 5, 6, 7};34 std::cout << "Before: ";35 printVec(data);36 heapSort(data);37 std::cout << "After: ";38 printVec(data);39 return 0;40}C로 구현한 Heap Sort 코드
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void siftDown(int a[], int n, int i) {9 while (1) {10 int largest = i, l = 2 * i + 1, r = 2 * i + 2;11 if (l < n && a[l] > a[largest]) largest = l;12 if (r < n && a[r] > a[largest]) largest = r;13 if (largest == i) return;14 int tmp = a[i];15 a[i] = a[largest];16 a[largest] = tmp;17 i = largest;18 }19}20
21void heapSort(int a[], int n) {22 // Build a max-heap in place23 for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);24 // Repeatedly move the max to the end and shrink the heap25 for (int end = n - 1; end > 0; end--) {26 int tmp = a[0];27 a[0] = a[end];28 a[end] = tmp;29 siftDown(a, end, 0);30 }31}32
33int main(void) {34 int data[] = {12, 11, 13, 5, 6, 7};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 heapSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}힙 정렬 자주 묻는 질문
힙 정렬의 시간 복잡도는 무엇인가요?
힙 정렬은 최선, 평균, 최악의 경우 모두
O(n log n)입니다. 힙 구축은 O(n)이며 n회의 추출 각각은 O(log n)의 비용이 듭니다. 추가 공간은 O(1)을 사용합니다.힙 정렬은 안정적인가요?
아니요. sift-down 연산은 동일한 원소를 서로 지나치게 이동시킬 수 있으므로, 힙 정렬은 동일한 키의 상대적 순서를 보존하지 않습니다.
힙 정렬은 언제 사용해야 하나요?
추가 메모리를
O(1)만 쓰면서 보장된 O(n log n) 최악의 경우가 필요할 때 힙 정렬을 사용하세요. 병합 정렬의 O(n) 버퍼 없이 퀵 정렬의 O(n²) 위험을 피할 수 있지만, 그 대가로 안정성과 캐시 성능을 잃습니다.힙 정렬과 퀵 정렬의 차이는 무엇인가요?
둘 다 제자리에서 정렬하지만, 퀵 정렬은
O(n²)의 최악의 경우가 있는 반면 힙 정렬은 O(n log n)을 보장합니다. 실제로는 퀵 정렬이 캐시 지역성이 좋고 교환이 적어 대개 더 빠르므로, 힙 정렬은 주로 최악의 경우 상한을 보장해야 할 때 선호됩니다.힙 정렬은 우선순위 큐와 어떻게 관련되나요?
이진 힙은 우선순위 큐의 표준 구현이며, 힙 정렬은 본질적으로 그 큐에서 최댓값을 반복적으로 꺼내는 것입니다. 데이터를 이미 힙으로 유지하고 있다면 원소를 하나씩 꺼내는 것만으로 정렬된 순서를 공짜로 얻을 수 있습니다.
힙 정렬에는 max-heap과 min-heap 중 무엇이 필요한가요?
제자리에서 오름차순으로 정렬하려면 max-heap을 사용하세요. 매 패스마다 가장 큰 원소가 끝으로 교환되어 정렬된 꼬리가 오른쪽에서 자라납니다. min-heap은 제자리에서 내림차순을 만들거나, 별도의 배열로 꺼내면 오름차순을 만듭니다.
관련 자료
더 많은 시각화
