힙 자료구조는 가장 큰 값이나 가장 작은 값을 자주 꺼내야 할 때 빛나는 구조입니다. 중요한 포인트는 트리 모양 자체보다, 왜 이 구조가 우선순위 큐와 잘 맞는지 이해하는 데 있습니다.
예를 들어 작업 스케줄러를 떠올려 보면 이해가 쉽습니다. 가장 급한 작업을 먼저 꺼내고 새 작업이 들어오면 다시 적당한 자리에 넣어야 하는데, 이때 매번 전체를 정렬하면 낭비가 큽니다. 힙은 바로 이런 장면에 맞춰진 자료구조입니다.
결론부터 말하면, 힙은 전체 순서를 다 맞추지 않고 루트에 가장 중요한 값만 빠르게 오게 유지하기 때문에 우선순위 큐에 잘 맞습니다. 이번 글에서는 완전 이진 트리 설명은 필요한 만큼만 하고, 삽입과 삭제가 왜 빠른지, 정렬이나 탐색과는 무엇이 다른지에 집중해서 설명하겠습니다.
힙 자료구조를 한 줄로 이해하기
힙은 부모와 자식 사이의 우선순위 관계만 지키는 트리 기반 구조입니다. 최소 힙이면 부모가 자식보다 작거나 같고, 최대 힙이면 부모가 자식보다 크거나 같습니다.
여기서 중요한 점은 힙이 배열 전체를 오름차순이나 내림차순으로 정렬해 두지 않는다는 것입니다. 대신 맨 위 루트 하나만은 정말 믿을 수 있게 관리합니다.
그래서 최소 힙에서는 가장 작은 값이 루트에 있고, 최대 힙에서는 가장 큰 값이 루트에 있습니다. 힙은 전체 정렬 구조가 아니라 루트 우선 구조입니다.
왜 우선순위 큐와 잘 맞을까
- 새 원소를 넣기
- 가장 우선순위가 높은 원소를 꺼내기
우선순위 큐에서 가장 자주 하는 일은 이 두 가지입니다. 여기서 중요한 건 전체를 순서대로 다 꺼내는 것이 아니라, 지금 당장 가장 중요한 하나를 빨리 꺼내는 일입니다.
힙은 이 요구와 아주 잘 맞습니다. 루트에 최댓값 또는 최솟값이 오도록 유지하므로 가장 중요한 원소를 확인하는 일은 매우 빠르고, 새 원소를 넣거나 루트를 꺼낸 뒤에도 트리 전체를 다시 정렬하지 않고 필요한 경로만 조금 고치면 됩니다.
- 정렬 배열은 전체 순서는 좋지만 삽입이 무거울 수 있습니다.
- 연결 리스트는 삽입 위치는 편할 수 있지만 최댓값이나 최솟값 찾기가 느립니다.
- 힙은 가장 중요한 값 하나를 자주 다루는 상황에 균형이 좋습니다.
그래서 언어 라이브러리의 PriorityQueue나 heapq도 보통 힙을 바탕으로 만들어집니다.
완전 이진 트리는 왜 필요할까
힙 설명을 들으면 늘 나오는 말이 완전 이진 트리입니다. 하지만 여기서 너무 오래 머물 필요는 없습니다. 핵심만 말하면, 노드를 왼쪽부터 빈칸 없이 채우는 모양이라서 트리 높이가 한쪽으로 심하게 늘어지지 않습니다.
그 덕분에 루트에서 아래로 내려가거나 아래에서 위로 올라가는 경로 길이가 짧게 유지됩니다. 삽입이나 삭제 때 힙이 빠른 이유는 결국 움직여야 하는 칸 수가 트리 높이 정도로 제한되기 때문입니다.
배열로 구현하기 쉬운 것도 큰 장점입니다. 부모와 자식 위치를 인덱스로 계산할 수 있어서 포인터 트리보다 구현이 단순합니다.
힙 삽입은 왜 빠를까
새 원소를 넣는 장면을 떠올려 보겠습니다. 최소 힙에 2, 4, 7, 9, 6이 있고 여기에 3을 넣는다고 해보겠습니다.
힙은 일단 맨 마지막 빈자리에 3을 넣고, 그다음 부모와 비교합니다. 부모보다 더 작다면 자리를 바꾸고, 이 과정을 위로 올라가며 반복합니다.
- 새 원소는 처음부터 완벽한 자리를 찾지 않습니다.
- 일단 끝에 붙입니다.
- 필요한 만큼만 위로 올라갑니다.
이 동작을 보통 sift up 또는 bubble up이라고 부릅니다. 즉, 삽입할 때 전체를 다시 정렬하지 않고 새 원소 하나가 지나가는 위쪽 경로만 손보면 끝입니다. 그래서 빠릅니다.
루트 삭제는 왜 빠를까
우선순위 큐에서 가장 중요한 연산은 보통 루트를 꺼내는 일입니다. 최소 힙이면 최솟값, 최대 힙이면 최댓값을 꺼내는 순간입니다.
- 루트 값을 꺼냅니다.
- 마지막 원소를 루트로 올립니다.
- 자식과 비교하면서 더 알맞은 자리로 내려보냅니다.
이 과정을 sift down이라고 생각하면 됩니다. 루트에 임시로 올라온 원소가 너무 크거나 너무 작으면 아래로 내려가며 자리를 찾는 것입니다.
삽입 때는 아래에서 위로 올라가고, 삭제 때는 위에서 아래로 내려갑니다. 하지만 둘 다 공통점이 있습니다. 트리 전체를 뒤엎지 않고 한 줄 경로만 고친다는 점입니다. 이게 힙의 속도 감각입니다.
시간 복잡도는 이렇게 기억하면 충분하다
- 루트 확인: O(1)
- 삽입: O(log n)
- 루트 삭제: O(log n)
- heapify: O(n)
가장 많이 헷갈리는 부분은 이것입니다. “힙은 빠르다”가 아니라, 가장 큰 값 또는 가장 작은 값을 반복해서 다룰 때 빠르다가 더 정확합니다.
모든 작업이 다 빠른 것은 아닙니다. 예를 들어 특정 값이 안에 있는지 찾는 일은 힙의 강점이 아닙니다. Java PriorityQueue의 contains가 선형 시간인 것도 같은 맥락입니다.
힙은 정렬과 무엇이 다를까
힙을 처음 배울 때 자주 생기는 오해가 있습니다. 루트가 가장 작거나 큰 값이면 나머지도 거의 정렬돼 있는 것처럼 느껴진다는 점입니다. 하지만 실제로는 그렇지 않습니다.
예를 들어 최소 힙에서는 루트가 가장 작다는 것만 확실합니다. 왼쪽 서브트리 전체와 오른쪽 서브트리 전체가 서로 정렬돼 있다는 보장은 없고, 형제 노드끼리도 크기 순서가 정리돼 있지 않을 수 있습니다.
그래서 힙 배열을 그냥 앞에서부터 읽는다고 정렬된 결과가 나오지 않습니다. 힙은 정렬 결과를 저장하는 구조가 아니라 우선순위가 가장 높은 원소를 빨리 꺼내기 위한 구조입니다.
정렬이 목적이라면 배열 정렬이나 힙 정렬 같은 다른 절차를 써야 합니다. 우선순위 큐가 목적이라면 힙이 잘 맞습니다.
힙은 탐색과도 다르다
힙을 이진 탐색 트리와 같은 부류로 착각하는 경우도 많습니다. 둘 다 트리처럼 보이기 때문입니다. 하지만 목표가 다릅니다.
- 이진 탐색 트리는 특정 값을 찾는 데 강합니다.
- 힙은 최댓값이나 최솟값을 꺼내는 데 강합니다.
이진 탐색 트리는 왼쪽과 오른쪽 서브트리의 값 범위가 강하게 정리됩니다. 그래서 특정 값을 찾을 때 방향을 과감하게 버릴 수 있습니다. 반면 힙은 부모와 자식 관계만 보장하므로, 중간 어딘가에 있는 값을 찾을 때는 그렇게 큰 도움을 주지 못합니다.
즉, 힙은 검색용 자료구조가 아니라 우선순위 관리용 자료구조라고 이해하는 편이 정확합니다.
짧은 예시로 보면 더 쉽다
파이썬의 heapq는 기본적으로 최소 힙입니다. 아래 코드를 보면 힙이 무엇을 잘하는지 금방 느껴집니다.
import heapq
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 2)
heapq.heappush(pq, 8)
heapq.heappush(pq, 3)
print(pq[0]) # 가장 작은 값 확인
print(heapq.heappop(pq))
print(heapq.heappop(pq))이 코드에서 중요한 것은 내부 배열 모양을 외우는 일이 아닙니다. 중요한 건 pq[0]으로 지금 가장 작은 값을 바로 확인할 수 있고, heappop()을 여러 번 하면 작은 값부터 차례대로 꺼낼 수 있다는 점입니다.
즉, 힙은 항상 전체를 보기보다 지금 가장 급한 원소를 먼저 꺼내는 흐름에 맞춰져 있습니다.
언제 힙을 떠올리면 좋을까
- 가장 작은 값 또는 가장 큰 값을 반복해서 꺼냅니다.
- 우선순위가 높은 작업부터 처리합니다.
- 실시간으로 값이 계속 들어옵니다.
- 상위 K개만 유지하고 싶습니다.
- 스케줄링, 이벤트 처리, 최단 경로 알고리즘 같은 흐름입니다.
대표적으로는 작업 스케줄러, Dijkstra 알고리즘, 이벤트 시뮬레이션, top K 문제에서 자주 등장합니다.
정리
힙 자료구조는 전체를 정렬해 두는 대신, 가장 중요한 값이 맨 위에 오도록 유지하는 구조입니다. 그래서 우선순위 큐처럼 삽입과 최댓값이나 최솟값 삭제가 반복되는 장면에서 특히 강합니다.
자료구조 기초를 함께 보고 싶다면 스택과 큐 차이, 해시 테이블이 빠른 이유, 이진 탐색 트리 글도 이어서 보면 차이가 더 잘 잡힙니다.
외부 참고 문서는 Python heapq 문서와 Oracle Java PriorityQueue 문서입니다.
