자료구조 - 힙과 우선순위큐

힙 자료구조 (우선순위큐, 정렬, 다익스트라)

이진 트리 위에 정렬 규칙을 얹으면 BST가 되고, 그와는 또 다른 규칙(부모가 자식보다 항상 크다 또는 작다)을 얹으면 힙(Heap)이 된다. 힙은 BST와는 완전히 다른 사용 시나리오를 가지는데, 임의 키 검색이 아니라 최댓값 또는 최솟값을 반복적으로 꺼내는 작업에 특화되어 있다. 이 단순한 규칙 하나로 힙은 우선순위 큐의 표준 구현체, 힙 정렬의 핵심 도구, 다익스트라 최단 경로의 가속기 역할을 동시에 수행한다. 본 글은 힙의 정의·연산·시간복잡도부터 우선순위 큐와 실전 응용까지 세심하게 정리한다(출처: 위키백과 — Heap (data structure)). 제가 학교 알고리즘 수업에서 다익스트라 알고리즘을 처음 배우며 가장 충격이었던 게 우선순위 큐 한 줄을 힙으로 갈아 끼우자 시간복잡도가 O(V²)에서 O((V+E) log V)로 떨어지는 모습이었고, 그 한 번의 비교가 힙의 가치를 손끝으로 가르쳐 주었다.

 

힙의 정의와 종류 — 최대힙·최소힙

힙(Heap)이란 다음 두 조건을 만족하는 완전 이진 트리(complete binary tree)이다. 첫째, 힙 속성(Heap Property) — 모든 부모 노드가 그 자식 노드보다 크거나(최대힙) 또는 작다(최소힙). 둘째, 완전성 — 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워진다. 이 두 조건이 결합되면 힙은 자연스럽게 배열로 표현 가능해지며, 그 자체가 가장 큰 강점이 된다.

힙은 정렬 방향에 따라 두 종류로 나뉜다.

종류	힙 속성	루트가 가지는 값	대표 응용
최대 힙(Max-Heap)	부모 ≥ 자식	전체에서 가장 큰 값	내림차순 힙 정렬, 우선순위 큐(가장 중요한 작업 먼저)
최소 힙(Min-Heap)	부모 ≤ 자식	전체에서 가장 작은 값	오름차순 힙 정렬, 다익스트라 최단 경로

여기서 힙 속성이란 부모-자식 사이에만 적용되는 부분 정렬 조건이며, 같은 레벨 안의 두 형제 사이에는 어떤 순서도 보장되지 않는다는 점이 BST와의 결정적 차이이다. BST가 전체 정렬을 보장하는 대신 임의 검색에 유리하다면, 힙은 부분 정렬만 유지하는 대신 최댓값(또는 최솟값) 추출에 특화되어 있다. 솔직히 이건 예상 밖이었는데, 학교에서 처음 힙을 배웠을 때 "왜 굳이 전체 정렬을 포기하는가" 의문이 들었지만, 최댓값만 반복적으로 꺼낼 거라면 나머지 순서를 모두 정렬할 필요가 없어 그만큼 시간이 절약된다는 사실을 직접 코드를 짜 보고 나서야 받아들였다.

힙을 배열로 표현하면 부모-자식 인덱스 관계가 단순한 산술 연산으로 정리된다. 인덱스 i부터 시작할 때 자식과 부모의 위치는 다음과 같다.

# 0-기반 인덱스 (Python·C에서 표준)
def left(i):   return 2 * i + 1
def right(i):  return 2 * i + 2
def parent(i): return (i - 1) // 2

# 1-기반 인덱스 (CLRS 교과서·시험 답안에서 자주 등장)
def left_1(i):   return 2 * i
def right_1(i):  return 2 * i + 1
def parent_1(i): return i // 2

시험 답안에서는 1-기반 인덱스가 자주 쓰이는데, 식이 더 단순하기 때문이다. 학교 자료구조 시험에서는 "노드 i의 왼쪽 자식 인덱스는?" 같은 단답형이 자주 나오므로 두 표기법을 모두 외워 두는 편이 안전했다.

힙의 핵심 연산과 시간복잡도

힙이 제공하는 두 가지 핵심 연산이 삽입(insert)과 추출(extract-min 또는 extract-max)이다. 두 연산 모두 힙 속성을 복원하기 위해 트리의 한쪽 경로를 따라 한 단계씩 비교·교환하는 패턴을 사용하며, 그 결과 두 연산 모두 O(log n) 시간에 끝난다. 이 시간복잡도가 힙의 모든 응용을 뒷받침한다.

삽입은 새 원소를 배열의 마지막 자리에 일단 추가한 뒤, 부모와 비교하면서 위로 올라가는 상향 조정(sift-up, percolate-up)을 수행한다. 추출은 루트(최댓값 또는 최솟값)를 꺼낸 뒤 마지막 원소를 루트 자리로 옮기고, 자식과 비교하면서 아래로 내려가는 하향 조정(sift-down, percolate-down)을 수행한다.

# 최소 힙(Min-Heap) — 배열 기반 구현
class MinHeap:
    def __init__(self):
        self.a = []

    def push(self, v):
        self.a.append(v)
        i = len(self.a) - 1
        while i > 0:                        # sift-up
            p = (i - 1) // 2
            if self.a[p] <= self.a[i]: break
            self.a[p], self.a[i] = self.a[i], self.a[p]
            i = p

    def pop(self):
        if not self.a: raise IndexError("empty")
        top = self.a[0]
        last = self.a.pop()
        if self.a:
            self.a[0] = last
            i, n = 0, len(self.a)
            while True:                     # sift-down
                l, r = 2*i+1, 2*i+2
                smallest = i
                if l < n and self.a[l] < self.a[smallest]: smallest = l
                if r < n and self.a[r] < self.a[smallest]: smallest = r
                if smallest == i: break
                self.a[i], self.a[smallest] = self.a[smallest], self.a[i]
                i = smallest
        return top

    def peek(self): return self.a[0] if self.a else None

힙의 시간복잡도를 표로 정리하면 다음과 같다.

연산	시간복잡도	비고
push (삽입)	O(log n)	상향 조정
pop (최댓값/최솟값 추출)	O(log n)	하향 조정
peek (최댓값/최솟값 조회)	O(1)	루트만 보면 됨
buildHeap (n개 원소로 힙 생성)	O(n)	의외로 O(n log n)이 아님
임의 키 검색	O(n)	BST와의 결정적 차이

buildHeap이 O(n)으로 분석되는 점이 자주 시험에 나오는 항목인데, n개의 push를 반복하면 O(n log n)이지만, 배열을 한 번에 받아 아래쪽 절반의 노드부터 sift-down을 수행하면 O(n)에 힙이 완성된다는 분석이 정확한 결론이다(출처: CLRS — Introduction to Algorithms). 솔직히 제 경험상 학교 시험에서 이 항목이 가장 자주 함정 문제로 출제되었고, "buildHeap = O(n)"이라는 한 줄을 외워 둔 사람만 정답을 맞추는 패턴이 반복되었다.

우선순위 큐와 실전 응용 — 힙 정렬·다익스트라

우선순위 큐(Priority Queue)는 FIFO가 아닌 "우선순위가 높은 원소가 먼저 나가는" 큐의 변형 ADT이다. 추상적으로는 인터페이스(push·pop·peek 세 연산)만 정의되어 있지만, 구현체는 거의 예외 없이 힙이다. 파이썬의 heapq, 자바의 PriorityQueue, C++의 std::priority_queue가 모두 힙 위에 서 있으며, 따라서 우선순위 큐를 배운다는 것은 사실상 힙을 배우는 것과 같다.

# 파이썬 표준 라이브러리 heapq — 최소 힙 기반 우선순위 큐
import heapq

tasks = []
heapq.heappush(tasks, (3, "이메일 답장"))     # (우선순위, 작업명)
heapq.heappush(tasks, (1, "프로덕션 배포"))
heapq.heappush(tasks, (2, "코드 리뷰"))

while tasks:
    priority, name = heapq.heappop(tasks)
    print(f"우선순위 {priority}: {name}")
# 출력:
# 우선순위 1: 프로덕션 배포
# 우선순위 2: 코드 리뷰
# 우선순위 3: 이메일 답장

heapq는 최소 힙만 제공하므로 최대 힙이 필요하면 우선순위에 -1을 곱해 넣고 꺼낼 때 다시 부호를 뒤집는 트릭이 표준이다.

힙의 가장 고전적인 응용 두 가지가 힙 정렬과 다익스트라 최단 경로이다. 힙 정렬(Heap Sort)은 n개의 원소를 힙에 넣고 n번 추출하는 단순한 알고리즘으로, 시간복잡도는 O(n log n)이며 추가 메모리 없이 제자리 정렬(in-place)이 가능하다는 강점을 가진다. 다만 같은 O(n log n)인 퀵 정렬에 비해 캐시 효율이 떨어져 실무에서는 표준 정렬 알고리즘으로 거의 채택되지 않는다.

import heapq
def heap_sort(arr):
    h = arr.copy()
    heapq.heapify(h)             # O(n)
    return [heapq.heappop(h) for _ in range(len(h))]   # n번 × O(log n)

print(heap_sort([5, 2, 8, 1, 9, 3]))   # [1, 2, 3, 5, 8, 9]

다익스트라 알고리즘(Dijkstra)은 가중치가 음수가 아닌 그래프에서 한 시작 노드부터 모든 노드까지의 최단 경로를 구하는 표준 알고리즘이다. 우선순위 큐 없이 구현하면 매 단계마다 미방문 노드 중 가장 가까운 노드를 선형 탐색해야 해서 O(V²)이지만, 최소 힙 기반 우선순위 큐를 쓰면 그 탐색이 O(log V)로 떨어져 전체 시간복잡도가 O((V + E) log V)로 개선된다. 솔직히 이건 예상 밖이었는데, 제가 학교 알고리즘 과제에서 같은 다익스트라를 두 가지 방식으로 짜 본 후 노드 수가 1000개를 넘는 그래프에서 우선순위 큐 버전이 그렇지 않은 버전보다 50배 빠른 결과가 나오는 모습을 본 후로는 "힙은 학문적 사치가 아니라 실전 가속기"라는 인상을 받아들였다. 우선순위 큐는 다익스트라 외에도 A* 알고리즘, 허프만 압축, K-way 병합, 이벤트 시뮬레이션, 스케줄러 같은 거의 모든 알고리즘 핵심에 등장하며, 자료구조 학습의 가장 결정적인 분기점 중 하나이다.

마지막으로 시험 답안에서 자주 쓰이는 정형 표현 하나를 정리해 두면, "힙은 완전 이진 트리이며 부모-자식 사이에 정해진 대소 관계(최대 힙 또는 최소 힙)를 만족한다. 삽입과 추출 모두 O(log n) 시간에 가능하며, 우선순위 큐의 표준 구현체로 활용된다"는 두 문장이 그것이다. 다음 글에서는 같은 트리 계열이 아닌, 키-값 매핑을 거의 O(1)로 처리하는 또 다른 핵심 자료구조인 해시 테이블을 이어 다룬다.

---

메타 디스크립션: 힙(Heap) 자료구조의 정의·종류(최대힙·최소힙)·시간복잡도와 우선순위 큐 구현, 그리고 힙 정렬·다익스트라 최단 경로 같은 실전 응용을 코드 예시와 함께 자료구조 입문자 관점에서 세심하게 정리합니다.