---
title: "이진 힙: 맨 앞의 최솟값을 빠르게 유지하는 배열"
author: "Lee"
published_at: "2026-10-20T06:05:03.307Z"
updated_at: "2026-09-30T09:28:36.629Z"
tags: ["컴퓨터공학","자료구조"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%EC%9D%B4%EC%A7%84-%ED%9E%99-%EB%A7%A8-%EC%95%9E%EC%9D%98-%EC%B5%9C%EC%86%9F%EA%B0%92%EC%9D%84-%EB%B9%A0%EB%A5%B4%EA%B2%8C-%EC%9C%A0%EC%A7%80%ED%95%98%EB%8A%94-%EB%B0%B0%EC%97%B4"
ai_assisted: false
---

# 이진 힙: 맨 앞의 최솟값을 빠르게 유지하는 배열

[원문](https://ariser.io/@writer_a1cd615ab19e/%EC%9D%B4%EC%A7%84-%ED%9E%99-%EB%A7%A8-%EC%95%9E%EC%9D%98-%EC%B5%9C%EC%86%9F%EA%B0%92%EC%9D%84-%EB%B9%A0%EB%A5%B4%EA%B2%8C-%EC%9C%A0%EC%A7%80%ED%95%98%EB%8A%94-%EB%B0%B0%EC%97%B4)

이진 힙은 완전 이진 트리 형태와 힙 순서 조건을 가진 자료구조다. 최소 힙에서는 부모 값이 자식 값보다 작거나 같다. 그래서 루트가 전체 최솟값이다. 형제끼리나 서로 다른 가지 사이에는 정렬 조건이 없으므로 전체 배열이 정렬되어 있지는 않다.

![루트 2의 최소 힙과 레벨 순서 배열 2·5·3·9·7·4·6](/api/v1/media/b6098015-9b27-41df-be96-1dc99bbd3441)

*최소 힙은 부모가 자식보다 크지 않도록 유지하며 배열 전체가 정렬된 것은 아니다.*

### 트리를 배열로 저장하기

0부터 시작하는 배열에서 i의 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2이고 부모는 (i-1)//2다. 마지막 층을 왼쪽부터 채우는 완전 트리이므로 빈칸 없이 배열로 표현할 수 있다. 명시적인 노드 포인터가 필요하지 않다.

새 값은 배열 끝에 추가한다. 부모보다 작으면 교환하며 올라가는 sift-up을 수행한다. [2,5,7,9]에 1을 넣으면 먼저 부모 5와, 다시 루트 2와 교환하여 조건을 복구한다. 영향을 받는 것은 새 원소부터 루트까지의 경로다.

### 최솟값 제거 뒤에는 내려간다

루트 값을 저장하고 마지막 값을 루트로 옮긴 다음 더 작은 자식과 비교해 내려보낸다. 두 자식 중 큰 쪽과 교환하면 다른 작은 자식 때문에 조건이 여전히 깨질 수 있다.

```python
def sift_down(values, start_index):
    parent = start_index
    size = len(values)
    while 2 * parent + 1 < size:
        smaller_child = 2 * parent + 1
        right_child = smaller_child + 1
        if right_child < size and values[right_child] < values[smaller_child]:
            smaller_child = right_child
        if values[parent] <= values[smaller_child]:
            break
        values[parent], values[smaller_child] = values[smaller_child], values[parent]
        parent = smaller_child
```

높이가 O(log n)이므로 삽입과 최소 제거는 O(log n), 최소 확인은 O(1)이다. 임의의 값 검색은 힙 조건만으로 한 가지를 골라 갈 수 없어 O(n)이 걸릴 수 있다. 이진 탐색 트리처럼 순서 검색이 되는 구조가 아니다.

배열 전체를 힙으로 만드는 과정은 마지막 내부 노드부터 sift-down하면 O(n)이다. 모든 노드가 log n만큼 내려가는 것이 아니라 대부분은 잎 근처에 있어 이동할 높이가 작다. n번 순차 삽입의 O(n log n) 상한과 구분해야 한다.

힙은 우선순위 큐, 상위 k개 선택, 힙 정렬에 쓰인다. 동일 우선순위의 삽입 순서를 보존하려면 별도 순번을 비교 키에 넣어야 한다. 저장한 원소의 우선순위를 외부에서 직접 바꾸면 힙 조건이 깨질 수 있으므로 변경 뒤 재정렬하는 API가 필요하다.

우선순위 감소를 자주 지원하려면 항목의 배열 위치를 함께 관리할 수 있다. 원소를 교환할 때마다 위치 맵도 갱신해야 다음 변경이 올바른 곳에서 sift-up을 시작한다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)
- [Princeton · Algorithms, 4th edition · Priority Queues](https://algs4.cs.princeton.edu/24pq/)