수많은 데이터 중에서 "가장 큰 값(최댓값)"이나 "가장 작은 값(최솟값)"을 최대한 빨리 찾아내야 한다면 어떤 방법을 쓰시겠습니까? 아마도 데이터를 정렬(Sorting)한 뒤 맨 앞이나 맨 뒤를 가져오는 방법을 떠올릴 것입니다. 하지만 정렬은 꽤 비용이 많이 드는 작업(O(n log n))입니다. 데이터가 수시로 추가되고 삭제되는 상황에서 매번 정렬을 다시 하는 것은 시스템 성능을 갉아먹는 주범이 됩니다.
이때 등장하는 구세주가 바로 힙(Heap)입니다. 힙은 "완벽하게 정렬할 필요 없이, 대장(최댓값/최솟값)만 빨리 뽑자!"라는 철학으로 만들어진 자료구조입니다. 우선순위 큐를 구현하는 핵심 엔진이기도 한 힙의 원리를 파헤쳐 봅니다.
1. 힙(Heap)이란? (완전 이진 트리 기반)
힙은 완전 이진 트리(Complete Binary Tree) 형태를 띠고 있습니다. 완전 이진 트리란 데이터가 루트부터 시작해서 왼쪽에서 오른쪽으로 빈틈없이 차곡차곡 채워진 트리를 말합니다. 구멍이 숭숭 뚫린 트리와 달리 배열(Array)로 구현하기에 아주 최적화된 구조입니다.
1-1. 힙의 두 가지 종류
힙은 목적에 따라 두 가지로 나뉩니다. 부모와 자식 간의 대소 관계 규칙만 다릅니다.
- 최대 힙 (Max Heap): "부모는 자식보다 무조건 크거나 같다." 따라서 루트 노드에는 전체 데이터 중 가장 큰 값이 위치하게 됩니다.
- 최소 힙 (Min Heap): "부모는 자식보다 무조건 작거나 같다." 따라서 루트 노드에는 전체 데이터 중 가장 작은 값이 위치하게 됩니다.
2. 힙 vs 이진 탐색 트리(BST) 차이점
많은 분들이 힙과 이진 탐색 트리를 헷갈려 합니다. 하지만 둘은 족보가 다릅니다.
- 이진 탐색 트리(BST): 왼쪽 자식 < 부모 < 오른쪽 자식. (좌우 정렬 중요) -> 탐색이 목적.
- 힙(Heap): 자식 < 부모. (왼쪽이 크든 오른쪽이 크든 상관없음, 위아래 관계만 중요) -> 최댓값 추출이 목적.
힙은 형제 노드끼리의 대소 관계는 신경 쓰지 않습니다. 오직 부모 자식 간의 서열만 확실하면 됩니다. 이를 '느슨한 정렬 상태(Semi-ordered)'라고 합니다.
3. 힙의 동작 원리 (데이터 삽입과 삭제)
힙이 최댓값을 찾는 속도는 O(1)입니다. 그냥 루트 노드를 가져오면 되니까요. 하지만 데이터를 넣거나 뺐을 때 힙의 구조를 다시 맞추는 과정(Heapify)이 필요하며, 이 과정은 트리의 높이만큼인 O(log n)이 걸립니다.
3-1. 데이터 삽입 (Up-Heap)
새로운 데이터는 일단 트리의 가장 마지막 자리에 놓습니다. 그리고 부모와 비교하여 자기가 더 크면(최대 힙 기준) 부모와 자리를 바꿉니다. 이 과정을 부모보다 작아지거나 루트에 도달할 때까지 반복하며 위로 올라갑니다.
3-2. 데이터 삭제 (Down-Heap)
힙에서는 보통 루트 노드(최댓값)만 삭제합니다. 루트가 사라지면 가장 마지막에 있던 노드를 루트 자리로 올립니다. 그리고 이제 자식들과 비교하여 자식이 더 크면 자리를 바꿉니다. 제 자리를 찾을 때까지 아래로 내려갑니다.
4. 힙은 언제 쓰는가?
힙은 전체를 정렬하는 것보다 최댓값/최솟값 몇 개만 빠르게 필요할 때 압도적인 성능을 발휘합니다.
- 우선순위 큐(Priority Queue) 구현: 응급실 환자 처리, OS 스케줄링 등.
- 힙 정렬(Heap Sort): 힙에 데이터를 다 넣었다가 하나씩 꺼내면 자동으로 정렬이 됩니다.
- 최단 경로 알고리즘 (Dijkstra): 현재 갈 수 있는 가장 가까운 노드를 찾을 때 최소 힙을 사용합니다.
1. 힙(Heap)은 최댓값이나 최솟값을 O(1)에 찾기 위해 고안된 완전 이진 트리입니다.
2. 최대 힙은 부모가 자식보다 크고, 최소 힙은 부모가 자식보다 작은 구조를 유지합니다.
3. 좌우 정렬이 중요한 BST와 달리, 상하(부모-자식) 관계만 중요시하는 느슨한 정렬 구조입니다.