힙(이진 힙)
마지막 업데이트
이진 힙은 가장 작은 값(최소 힙) 또는 가장 큰 값(최대 힙)을 루트에 유지하는 완전 이진 트리입니다. 이 시각화는 최소 힙으로, 모든 부모는 자식보다 작거나 같습니다. 값을 추가하려면 다음 빈 자리에 붙인 다음, 부모보다 작은 동안 부모와 교환하며 "위로 끌어올려" 힙 속성이 다시 성립할 때까지 반복합니다. 위의 재생 버튼을 눌러 각 새 값이 제자리로 떠오르는 모습을 확인하세요.
힙은 완전 트리이므로 배열에 조밀하게 저장됩니다. 노드 i의 자식은 2i+1과 2i+2에 있습니다. 삽입과 최소값 제거는 O(log n)(루트에서 리프까지의 한 경로)이고, 최소값 조회는 O(1)인데, 이는 우선순위 큐가 필요로 하는 바로 그것입니다.
시간 및 공간 복잡도
| 연산 | 복잡도 | 비고 |
|---|---|---|
| 최소/최대 조회 | O(1) | 항상 루트임 |
| 삽입(push) | O(log n) | 한 경로를 따라 위로 끌어올림 |
| 최소/최대 제거 | O(log n) | 한 경로를 따라 아래로 내림 |
| 힙 구축 | O(n) | 한 번에 heapify |
| 공간 | O(n) | 배열 기반, 포인터 없음 |
단계별(push)
| 단계 | 무슨 일이 일어나는가 |
|---|---|
| 1 | 새 값을 끝(다음 빈 리프)에 붙인다. |
| 2 | 그 값을 부모와 비교한다. |
| 3 | 더 작으면(최소 힙) 위로 교환한다. |
| 4 | 더 이상 부모보다 작지 않거나 루트에 도달할 때까지 반복한다. |
예제 풀이
[5, 3, 8, 1, 4]를 한 값씩 삽입하여 최소 힙을 구축하기:
| Push | 끌어올린 후 배열 | 동작 |
|---|---|---|
5 | [5] | 첫 번째 값이 루트가 된다. |
3 | [3, 5] | 3 < 부모 5이므로 루트까지 올라간다. |
8 | [3, 5, 8] | 8 > 부모 5이므로 리프로 남는다. |
1 | [1, 3, 8, 5] | 1 < 부모 5로 교환, 이어서 1 < 부모 3으로 루트까지 올라간다. |
4 | [1, 3, 8, 5, 4] | 4 > 부모 3이므로 남는다. 최소값 1은 루트에 남는다. |
힙을 사용할 때
| 사용할 때 | 피할 때 |
|---|---|
| 변화하는 집합에서 가장 작거나 큰 항목이 반복적으로 필요할 때. | 극값뿐 아니라 임의의 값을 검색해야 할 때 - BST나 해시 집합을 사용하라. |
| Dijkstra, A*, 스케줄러를 위한 우선순위 큐를 구현할 때. | 데이터를 항상 완전히 정렬된 상태로 유지해야 할 때. |
조밀한 배열 레이아웃으로 O(log n) 삽입과 최소값 제거를 원할 때. | 특정한(루트가 아닌) 원소를 빠르게 조회하거나 삭제해야 할 때. |
| 항목 스트림을 병합하고 우선순위대로 꺼내야 할 때. | 데이터 집합이 아주 작고 선형 탐색이 더 단순하며 충분히 빠를 때. |
Heap (Priority Queue) 코드
Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Heap (Priority Queue) 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.
Python로 구현한 Heap (Priority Queue) 코드
Python
1class MinHeap:2 def __init__(self):3 self.data = []4
5 def push(self, value):6 # Append at the end, then bubble up to restore order7 self.data.append(value)8 i = len(self.data) - 19 while i > 0:10 parent = (i - 1) // 211 if self.data[parent] <= self.data[i]:12 break13 self.data[i], self.data[parent] = self.data[parent], self.data[i]14 i = parent15
16 def pop(self):17 # Move the last leaf to the root, then sift it down18 top = self.data[0]19 last = self.data.pop()20 if self.data:21 self.data[0] = last22 self._sift_down(0)23 return top24
25 def _sift_down(self, i):26 n = len(self.data)27 while True:28 smallest = i29 left, right = 2 * i + 1, 2 * i + 230 if left < n and self.data[left] < self.data[smallest]:31 smallest = left32 if right < n and self.data[right] < self.data[smallest]:33 smallest = right34 if smallest == i:35 return36 self.data[i], self.data[smallest] = self.data[smallest], self.data[i]37 i = smallest38
39
40heap = MinHeap()41for value in [5, 3, 8, 1, 9, 2]:42 heap.push(value)43
44print("Heap array: ", heap.data)45print("Popped in order:", [heap.pop() for _ in range(6)])JavaScript로 구현한 Heap (Priority Queue) 코드
JavaScript
1class MinHeap {2 constructor() {3 this.items = [];4 }5
6 push(value) {7 this.items.push(value);8 // Bubble the new value up while it is smaller than its parent9 let i = this.items.length - 1;10 while (i > 0) {11 const parent = Math.floor((i - 1) / 2);12 if (this.items[parent] <= this.items[i]) break;13 [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];14 i = parent;15 }16 }17
18 pop() {19 const top = this.items[0];20 const last = this.items.pop();21 if (this.items.length > 0) {22 this.items[0] = last;23 this.sinkDown(0);24 }25 return top;26 }27
28 sinkDown(i) {29 const n = this.items.length;30 while (true) {31 let smallest = i;32 const left = 2 * i + 1;33 const right = 2 * i + 2;34 if (left < n && this.items[left] < this.items[smallest]) smallest = left;35 if (right < n && this.items[right] < this.items[smallest]) smallest = right;36 if (smallest === i) return;37 [this.items[i], this.items[smallest]] = [this.items[smallest], this.items[i]];38 i = smallest;39 }40 }41}42
43const heap = new MinHeap();44for (const value of [5, 2, 9, 1, 7, 3]) heap.push(value);45const sorted = [];46while (heap.items.length > 0) sorted.push(heap.pop());47console.log("Popped in order:", sorted.join(" "));Java로 구현한 Heap (Priority Queue) 코드
Java
1public class Main {2 static int[] heap = new int[32];3 static int size = 0;4
5 static void push(int value) {6 heap[size] = value;7 int i = size++;8 // Sift up while smaller than the parent9 while (i > 0 && heap[(i - 1) / 2] > heap[i]) {10 swap(i, (i - 1) / 2);11 i = (i - 1) / 2;12 }13 }14
15 static int pop() {16 int min = heap[0];17 heap[0] = heap[--size];18 int i = 0;19 // Sift down: swap with the smaller child until in place20 while (true) {21 int smallest = i, l = 2 * i + 1, r = 2 * i + 2;22 if (l < size && heap[l] < heap[smallest]) smallest = l;23 if (r < size && heap[r] < heap[smallest]) smallest = r;24 if (smallest == i) break;25 swap(i, smallest);26 i = smallest;27 }28 return min;29 }30
31 static void swap(int a, int b) {32 int tmp = heap[a];33 heap[a] = heap[b];34 heap[b] = tmp;35 }36
37 public static void main(String[] args) {38 int[] values = {9, 4, 7, 1, 8, 2};39 for (int v : values) push(v);40 System.out.print("Popped in order:");41 while (size > 0) System.out.print(" " + pop());42 System.out.println();43 }44}C++로 구현한 Heap (Priority Queue) 코드
C++
1#include <iostream>2#include <utility>3#include <vector>4
5struct MinHeap {6 std::vector<int> data;7
8 void push(int value) {9 data.push_back(value);10 // Sift up until the parent is no larger11 size_t i = data.size() - 1;12 while (i > 0) {13 size_t parent = (i - 1) / 2;14 if (data[parent] <= data[i]) break;15 std::swap(data[parent], data[i]);16 i = parent;17 }18 }19
20 int pop() {21 int top = data[0];22 data[0] = data.back();23 data.pop_back();24 // Sift down: swap with the smaller child25 size_t i = 0;26 while (true) {27 size_t l = 2 * i + 1, r = 2 * i + 2, smallest = i;28 if (l < data.size() && data[l] < data[smallest]) smallest = l;29 if (r < data.size() && data[r] < data[smallest]) smallest = r;30 if (smallest == i) break;31 std::swap(data[i], data[smallest]);32 i = smallest;33 }34 return top;35 }36
37 int peek() const { return data[0]; }38 bool empty() const { return data.empty(); }39};40
41int main() {42 MinHeap heap;43 for (int value : {5, 3, 8, 1, 9, 2}) heap.push(value);44 std::cout << "Min: " << heap.peek() << "\n";45 std::cout << "Popped in order: ";46 while (!heap.empty()) std::cout << heap.pop() << " ";47 std::cout << "\n";48 return 0;49}C로 구현한 Heap (Priority Queue) 코드
C
1#include <stdio.h>2
3#define CAP 644
5int heap[CAP];6int heapSize = 0;7
8void push(int value) {9 // Sift up until the parent is no larger10 int i = heapSize++;11 heap[i] = value;12 while (i > 0) {13 int parent = (i - 1) / 2;14 if (heap[parent] <= heap[i]) break;15 int tmp = heap[parent];16 heap[parent] = heap[i];17 heap[i] = tmp;18 i = parent;19 }20}21
22int pop(void) {23 int top = heap[0];24 heap[0] = heap[--heapSize];25 // Sift down: swap with the smaller child26 int i = 0;27 while (1) {28 int l = 2 * i + 1, r = 2 * i + 2, smallest = i;29 if (l < heapSize && heap[l] < heap[smallest]) smallest = l;30 if (r < heapSize && heap[r] < heap[smallest]) smallest = r;31 if (smallest == i) break;32 int tmp = heap[i];33 heap[i] = heap[smallest];34 heap[smallest] = tmp;35 i = smallest;36 }37 return top;38}39
40int main(void) {41 int values[] = {5, 3, 8, 1, 9, 2};42 for (int i = 0; i < 6; i++) push(values[i]);43 printf("Min: %d\n", heap[0]);44 printf("Popped in order: ");45 while (heapSize > 0) printf("%d ", pop());46 printf("\n");47 return 0;48}힙 자주 묻는 질문
힙은 무엇에 사용되나요?
힙은 우선순위 큐를 구현하며, 이는 Dijkstra의 최단 경로 알고리즘, 작업 스케줄러, 이벤트 시뮬레이션을 구동합니다. 또한 힙 정렬의 엔진이기도 합니다. 변화하는 집합에서 가장 작거나 큰 항목이 반복적으로 필요할 때면 언제나 힙이 알맞은 도구입니다.
힙과 이진 탐색 트리의 차이는 무엇인가요?
둘 다 이진 트리이지만, BST는 왼쪽에서 오른쪽으로의 완전한 정렬 순서를 유지하여(정렬된 탐색을 가능하게 함) 반면 힙은 부모-자식 관계만(루트에 최소 또는 최대) 보장합니다. 힙은 극값에 O(1) 접근을 제공하고, BST는 임의의 값에 O(log n) 탐색을 제공합니다.
힙은 왜 배열에 저장되나요?
힙은 항상 완전 이진 트리이므로, 그 노드는 배열 인덱스에 완벽하게 대응됩니다. 인덱스
i의 자식은 2i+1과 2i+2에 있고, 부모는 (i-1)/2에 있습니다. 이는 자식 포인터 저장을 피하게 하고 뛰어난 캐시 성능을 제공합니다.힙은 정렬된 배열과 같은가요?
아닙니다. 힙은 각 부모가 자식보다 작거나(최소 힙) 크다는(최대 힙) 것만 보장하므로 형제와 사촌은 특정한 순서가 없습니다. 정렬된 배열은 완전히 정렬되어 있지만 삽입에
O(n)이 들고, 힙은 O(log n)에 삽입하면서도 극값에 즉시 접근할 수 있습니다.배열을 그냥 정렬하는 대신 언제 힙을 사용해야 하나요?
데이터가 계속 바뀌고 현재의 최소값이나 최대값만 필요할 때 힙을 선택하세요. 삽입과 꺼내기는 각각
O(log n)으로, 전체 배열을 다시 정렬하는 것보다 유리합니다. 정적인 데이터 집합에서 모든 원소를 순서대로 원한다면, 한 번의 O(n log n) 정렬이 더 단순하고 흔히 더 빠릅니다.n개의 항목으로 힙을 구축하면 O(n log n)이 걸리나요?
한 번에 구축하면 그렇지 않습니다.
n개의 항목을 하나씩 삽입하면 O(n log n)이지만, 마지막 부모에서 루트로 아래로 내리는 상향식 heapify는 전체적으로 O(n)에 실행됩니다. 대부분의 노드가 바닥 근처에 있어 짧은 거리만 내려가기 때문입니다.관련 자료
더 많은 시각화
