힙 자료구조 이해하기
소개
힙(Heap)은 특정한 규칙을 만족하는 트리 기반 자료구조로, 우선순위 큐, 그래프 알고리즘(예: 다익스트라 알고리즘), 정렬(예: 힙 정렬) 등에 널리 사용됩니다. 힙에는 두 가지 주요 유형이 있습니다:
- 최소 힙(Min-Heap): 부모 노드는 항상 자식 노드보다 작거나 같습니다.
- 최대 힙(Max-Heap): 부모 노드는 항상 자식 노드보다 크거나 같습니다.
힙의 특징
- 힙은 보통 이진 힙(Binary Heap)으로 구현되며, 완전 이진 트리(Complete Binary Tree)의 형태를 가집니다.
- 루트 노드는 항상 최소값(최소 힙) 또는 최대값(최대 힙)을 포함합니다.
- 삽입 및 삭제 연산 시 힙 속성을 유지해야 합니다.
힙 연산
1. 삽입(Insertion)
- 새 요소를 트리의 마지막 위치에 삽입합니다.
- 상향 힙 정렬(Heapify Up, Bubble Up): 삽입된 요소를 부모와 비교하여 필요 시 교환하며 힙 속성을 유지합니다.
2. 삭제(Extract Min/Max)
- 루트 노드(최소값 또는 최대값)를 제거합니다.
- 마지막 노드를 루트로 이동합니다.
- 하향 힙 정렬(Heapify Down, Bubble Down): 루트에서 시작하여 자식과 비교 후 교환하며 힙 속성을 유지합니다.
3. 힙 생성(Heapify)
- 정렬되지 않은 배열을 힙 구조로 변환합니다.
- 마지막 비단말 노드에서 시작하여 하향 힙 정렬을 적용합니다.
- 시간 복잡도: O(n)
구현 예제
파이썬 코드:
import heapq
# 최소 힙 예제
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 2)
heapq.heappush(min_heap, 8)
print(heapq.heappop(min_heap)) # 출력: 2 (최소값)
# 최대 힙 예제 (음수값 활용)
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -2)
heapq.heappush(max_heap, -8)
print(-heapq.heappop(max_heap)) # 출력: 8 (최대값)힙의 활용
- 우선순위 큐(Priority Queue): 작업 스케줄링, 다익스트라 최단 경로 알고리즘 등에 사용됩니다.
- 힙 정렬(Heapsort): O(n log n) 복잡도를 가지는 정렬 알고리즘입니다.
- 그래프 알고리즘: 프림(Prim) 알고리즘, 다익스트라 알고리즘에서 최적의 경로를 찾는 데 활용됩니다.
결론
힙은 효율적인 데이터 관리와 우선순위 처리를 위해 중요한 자료구조입니다. 힙 연산을 이해하고 활용하면 다양한 알고리즘 문제를 효율적으로 해결할 수 있습니다.