최소 힙 vs 최대 힙 완벽비교 (삽입, 삭제 과정)

컴퓨터 과학에서 힙(Heap)은 최댓값이나 최솟값을 빠르게 찾아내기 위해 고안된 완전 이진 트리(Complete Binary Tree) 기반의 자료구조입니다. 일반적인 이진 탐색 트리(BST)가 데이터의 탐색에 최적화되어 있다면, 힙은 데이터의 우선순위 관리에 특화되어 있습니다. 특히 삽입과 삭제 연산이 일어날 때마다 스스로 구조를 재정렬하는 자가 균형 기능을 갖추고 있어, 우선순위 큐(Priority Queue)나 힙 정렬(Heap Sort)의 핵심 엔진으로 사용됩니다. 이 글에서는 최소 힙과 최대 힙의 구조적 차이점을 분석하고, 데이터가 추가되고 삭제되는 내부 매커니즘을 상세히 다룹니다.

1. 최소 힙(Min Heap) vs 최대 힙(Max Heap) 개념 정의

힙의 종류는 부모 노드와 자식 노드 간의 크기 관계에 따라 크게 두 가지로 나뉩니다. 두 구조 모두 완전 이진 트리의 형태를 유지해야 한다는 공통점이 있습니다.

1-1. 최소 힙 (Min Heap)

규칙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같습니다.
특징: 루트 노드에는 전체 트리에서 가장 작은 값이 위치합니다. 최솟값을 O(1)의 시간 복잡도로 즉시 확인할 수 있습니다.

1-2. 최대 힙 (Max Heap)

규칙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같습니다.
특징: 루트 노드에는 전체 트리에서 가장 큰 값이 위치합니다. 최댓값을 O(1)의 시간 복잡도로 즉시 확인할 수 있습니다.

2. 힙의 데이터 삽입 과정 (Up-Heap)

새로운 데이터가 들어오면 힙은 완전 이진 트리의 형태를 깨뜨리지 않으면서 힙의 규칙을 만족시키기 위해 Up-Heap(또는 Bubble-up) 과정을 거칩니다. 최대 힙을 기준으로 설명하면 다음과 같습니다.

삽입: 새로운 노드를 트리의 가장 마지막 위치(가장 하단 왼쪽부터 채움)에 추가합니다.
비교: 추가된 노드와 부모 노드의 값을 비교합니다.
교환: 만약 추가된 노드가 부모보다 크다면 위치를 서로 바꿉니다(Swap).
반복: 부모 노드가 더 크거나 루트 노드에 도달할 때까지 이 과정을 반복합니다.

이 과정은 트리의 높이에 비례하여 수행되므로 시간 복잡도는 O(log N)입니다.

3. 힙의 데이터 삭제 과정 (Down-Heap)

힙에서 삭제 연산은 항상 루트 노드의 데이터를 가져오는 것을 의미합니다. 루트가 비어버리면 트리의 구조가 무너지므로, 이를 보완하기 위해 Down-Heap(또는 Heapify-down) 과정을 수행합니다.

삭제: 루트 노드(최대/최솟값)를 반환하고 제거합니다.
대체: 트리의 가장 마지막 노드를 루트 자리로 옮깁니다.
비교: 새로운 루트 노드와 자식 노드들의 값을 비교합니다.
교환: 자식 노드 중 더 큰(최대 힙 기준) 값과 위치를 바꿉니다.
반복: 힙의 규칙이 만족될 때까지 아래로 내려가며 반복합니다.

삭제 역시 트리의 높이에 비례하는 O(log N)의 시간 복잡도를 가집니다.

4. 파이썬(Python)을 이용한 힙 연산 구현

파이썬의 heapq 모듈은 기본적으로 최소 힙으로 동작합니다. 만약 최대 힙을 구현하고 싶다면 데이터에 마이너스(-) 부호를 붙여 우선순위를 반전시키는 트릭을 사용합니다.


import heapq

# 1. 최소 힙 생성 및 삽입
min_heap = []
heapq.heappush(min_heap, 10)
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 20)

print(f"최소 힙 루트(최솟값): {min_heap[0]}") # 5 출력

# 2. 최대 힙 구현 (부호 반전 트릭)
max_heap = []
values = [10, 5, 20]
for v in values:
    heapq.heappush(max_heap, -v)

# 꺼낼 때 다시 마이너스를 붙여 원복
print(f"최대 힙 루트(최댓값): {-heapq.heappop(max_heap)}") # 20 출력

[핵심 요약 : 최소 힙 vs 최대 힙]
1. 정의: 루트에 최솟값이 있으면 최소 힙, 최댓값이 있으면 최대 힙입니다.
2. 성능: 삽입과 삭제 모두 O(log N)의 효율적인 속도를 보장합니다.
3. 응용: 단순 검색보다는 데이터가 계속 추가/삭제되는 환경에서 최댓값 또는 최솟값을 반복적으로 찾아야 할 때 최적의 선택입니다.

kguidebook0001 님의 블로그