힙(이진 힙)

Q: 힙은 왜 배열에 저장되나요?

힙은 항상 완전 이진 트리이므로, 그 노드는 배열 인덱스에 완벽하게 대응됩니다. 인덱스 `i`의 자식은 `2i+1`과 `2i+2`에 있고, 부모는 `(i-1)/2`에 있습니다. 이는 자식 포인터 저장을 피하게 하고 뛰어난 캐시 성능을 제공합니다.

Q: 배열을 그냥 정렬하는 대신 언제 힙을 사용해야 하나요?

데이터가 계속 바뀌고 현재의 최소값이나 최대값만 필요할 때 힙을 선택하세요. 삽입과 꺼내기는 각각 `O(log n)`으로, 전체 배열을 다시 정렬하는 것보다 유리합니다. 정적인 데이터 집합에서 모든 원소를 순서대로 원한다면, 한 번의 `O(n log n)` 정렬이 더 단순하고 흔히 더 빠릅니다.

Q: n개의 항목으로 힙을 구축하면 O(n log n)이 걸리나요?

한 번에 구축하면 그렇지 않습니다. `n`개의 항목을 하나씩 삽입하면 `O(n log n)`이지만, 마지막 부모에서 루트로 아래로 내리는 상향식 `heapify`는 전체적으로 `O(n)`에 실행됩니다. 대부분의 노드가 바닥 근처에 있어 짧은 거리만 내려가기 때문입니다.

마지막 업데이트 2026년 7월 1일

이진 힙은 가장 작은 값(최소 힙) 또는 가장 큰 값(최대 힙)을 루트에 유지하는 완전 이진 트리입니다. 이 시각화는 최소 힙으로, 모든 부모는 자식보다 작거나 같습니다. 값을 추가하려면 다음 빈 자리에 붙인 다음, 부모보다 작은 동안 부모와 교환하며 "위로 끌어올려" 힙 속성이 다시 성립할 때까지 반복합니다. 위의 재생 버튼을 눌러 각 새 값이 제자리로 떠오르는 모습을 확인하세요.

힙은 완전 트리이므로 배열에 조밀하게 저장됩니다. 노드 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)])
이 코드를 Python 플레이그라운드에서 실행하기

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(" "));
이 코드를 JavaScript 플레이그라운드에서 실행하기

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}
이 코드를 Java 플레이그라운드에서 실행하기

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++ 플레이그라운드에서 실행하기

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}
이 코드를 C 플레이그라운드에서 실행하기

힙 자주 묻는 질문

힙은 무엇에 사용되나요?

힙은 우선순위 큐를 구현하며, 이는 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)에 실행됩니다. 대부분의 노드가 바닥 근처에 있어 짧은 거리만 내려가기 때문입니다.