개념
힙(Heap) - 완전 이진 트리 기반의 자료구조
부모와 자식 노드 간에 일정한 대소 관계를 유지
시간복잡도
| 연산 | 시간복잡도 |
|---|---|
| 삽입 | O(log n) |
| 삭제 | O(log n) |
| 최댓값/최솟값 조회 | O(1) |
| 힙 생성 | O(n) |
특징
힙의 종류
-
최대 힙 (Max Heap)
- 부모 노드 ≥ 자식 노드
- 루트: 최댓값
-
최소 힙 (Min Heap)
- 부모 노드 ≤ 자식 노드
- 루트: 최솟값
힙의 성질
최대 힙 예시:
100
/ \
19 36
/ \ /
17 3 25
최소 힙 예시:
1
/ \
3 5
/ \ /
9 10 8
장점
- 빠른 최댓값/최솟값 접근: O(1)
- 효율적인 우선순위 관리: O(log n)
- 완전 이진 트리: 배열로 효율적 구현
단점
- 검색 비효율적: O(n)
- 정렬된 상태 아님: 최상위 노드만 보장
Python 구현
1. heapq 모듈 (최소 힙)
import heapq
# 빈 힙 생성
heap = []
# 삽입
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap) # [1, 3, 7, 4]
# 최솟값 삭제 및 반환
min_val = heapq.heappop(heap)
print(min_val) # 1
print(heap) # [3, 4, 7]
# 최솟값 조회 (삭제 X)
print(heap[0]) # 3
# 시간복잡도: O(log n)2. 리스트를 힙으로 변환
import heapq
# 일반 리스트
arr = [4, 1, 7, 3, 8, 5]
# 힙으로 변환
heapq.heapify(arr)
print(arr) # [1, 3, 5, 4, 8, 7]
# 시간복잡도: O(n)3. 최대 힙 구현
import heapq
# 방법 1: 음수로 변환
max_heap = []
heapq.heappush(max_heap, -4)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -7)
max_val = -heapq.heappop(max_heap)
print(max_val) # 7
# 방법 2: 튜플 활용 (우선순위, 값)
max_heap = []
heapq.heappush(max_heap, (-4, 4))
heapq.heappush(max_heap, (-1, 1))
heapq.heappush(max_heap, (-7, 7))
priority, val = heapq.heappop(max_heap)
print(val) # 74. 힙 직접 구현
class MinHeap:
def __init__(self):
self.heap = []
def push(self, val):
self.heap.append(val)
self._heapify_up(len(self.heap) - 1)
def pop(self):
if not self.heap:
return None
# 루트와 마지막 원소 교환
self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
min_val = self.heap.pop()
if self.heap:
self._heapify_down(0)
return min_val
def _heapify_up(self, idx):
parent = (idx - 1) // 2
if idx > 0 and self.heap[idx] < self.heap[parent]:
self.heap[idx], self.heap[parent] = self.heap[parent], self.heap[idx]
self._heapify_up(parent)
def _heapify_down(self, idx):
smallest = idx
left = 2 * idx + 1
right = 2 * idx + 2
if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
smallest = left
if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest != idx:
self.heap[idx], self.heap[smallest] = self.heap[smallest], self.heap[idx]
self._heapify_down(smallest)
# 테스트
heap = MinHeap()
heap.push(4)
heap.push(1)
heap.push(7)
print(heap.pop()) # 1자주 나오는 문제 유형
1. K번째 큰 수 찾기
문제: 배열에서 K번째로 큰 수 찾기
import heapq
def find_kth_largest(nums, k):
# 방법 1: 최소 힙 사용 (크기 k 유지)
heap = nums[:k]
heapq.heapify(heap)
for num in nums[k:]:
if num > heap[0]:
heapq.heapreplace(heap, num)
return heap[0]
# 테스트
print(find_kth_largest([3, 2, 1, 5, 6, 4], 2)) # 5
# 시간복잡도: O(n log k)
# 공간복잡도: O(k)2. 배열을 힙으로 정렬
문제: 힙 정렬 구현
import heapq
def heap_sort(arr):
# 최소 힙으로 정렬
heapq.heapify(arr)
return [heapq.heappop(arr) for _ in range(len(arr))]
# 내림차순 정렬
def heap_sort_desc(arr):
# 음수로 변환하여 최대 힙처럼 사용
arr = [-x for x in arr]
heapq.heapify(arr)
return [-heapq.heappop(arr) for _ in range(len(arr))]
# 테스트
print(heap_sort([3, 1, 4, 1, 5, 9, 2])) # [1, 1, 2, 3, 4, 5, 9]
print(heap_sort_desc([3, 1, 4, 1, 5, 9, 2])) # [9, 5, 4, 3, 2, 1, 1]
# 시간복잡도: O(n log n)3. 두 개의 힙으로 중앙값 찾기
문제: 스트림에서 중앙값 실시간 계산
import heapq
class MedianFinder:
def __init__(self):
# 최대 힙 (작은 값들)
self.small = []
# 최소 힙 (큰 값들)
self.large = []
def add_num(self, num):
# 최대 힙에 추가 (음수로 변환)
heapq.heappush(self.small, -num)
# 균형 맞추기
if self.small and self.large and (-self.small[0] > self.large[0]):
heapq.heappush(self.large, -heapq.heappop(self.small))
# 크기 균형
if len(self.small) > len(self.large) + 1:
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
def find_median(self):
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2
# 테스트
mf = MedianFinder()
mf.add_num(1)
mf.add_num(2)
print(mf.find_median()) # 1.5
mf.add_num(3)
print(mf.find_median()) # 2
# 시간복잡도: O(log n) - 삽입, O(1) - 조회4. 합병 K개의 정렬된 리스트
문제: K개의 정렬된 연결 리스트를 하나로 합치기
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_k_lists(lists):
heap = []
# 각 리스트의 첫 노드를 힙에 추가
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode()
current = dummy
while heap:
val, i, node = heapq.heappop(heap)
current.next = node
current = current.next
# 다음 노드를 힙에 추가
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
# 시간복잡도: O(N log k) - N: 전체 노드 수, k: 리스트 개수5. 상위 K개 빈도 수
문제: 배열에서 가장 빈번한 K개의 원소 찾기
import heapq
from collections import Counter
def top_k_frequent(nums, k):
# 빈도 계산
count = Counter(nums)
# 빈도를 음수로 최대 힙처럼 사용
return heapq.nlargest(k, count.keys(), key=count.get)
# 테스트
print(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) # [1, 2]
print(top_k_frequent([1], 1)) # [1]
# 시간복잡도: O(n log k)추천 연습 문제
기초
중급
- 백준 11286번 - 절댓값 힙
- LeetCode 295 - Find Median from Data Stream
- LeetCode 347 - Top K Frequent Elements
고급
핵심 요약
| 개념 | 설명 |
|---|---|
| 힙 | 완전 이진 트리 기반 자료구조 |
| 최소 힙 | 부모 ≤ 자식 (루트: 최솟값) |
| 최대 힙 | 부모 ≥ 자식 (루트: 최댓값) |
| 주요 연산 | 삽입/삭제 O(log n), 조회 O(1) |
heapq 주요 함수
import heapq
# 삽입
heapq.heappush(heap, item)
# 삭제 (최솟값)
heapq.heappop(heap)
# 조회 (최솟값)
heap[0]
# 리스트를 힙으로 변환
heapq.heapify(list)
# 삭제 후 삽입
heapq.heapreplace(heap, item)
# 삽입 후 삭제
heapq.heappushpop(heap, item)
# 최대 n개
heapq.nlargest(n, iterable, key=None)
# 최소 n개
heapq.nsmallest(n, iterable, key=None)힙 vs 다른 자료구조
| 자료구조 | 최댓값/최솟값 | 삽입 | 삭제 | 검색 |
|---|---|---|---|---|
| 힙 | O(1) | O(log n) | O(log n) | O(n) |
| 배열 (정렬) | O(1) | O(n) | O(n) | O(log n) |
| BST | O(log n) | O(log n) | O(log n) | O(log n) |
활용 분야
1. 우선순위 큐
- 작업 스케줄링
- 이벤트 시뮬레이션
2. 정렬
- 힙 정렬
- 부분 정렬
3. 그래프 알고리즘
- 다익스트라 최단 경로
- 프림 MST
4. 스트림 데이터
- 실시간 중앙값
- 상위 K개 찾기
주의사항
1. Python heapq는 최소 힙만 지원
# 최대 힙이 필요하면 음수 변환
heapq.heappush(heap, -value)
max_val = -heapq.heappop(heap)2. 힙은 부분적으로만 정렬됨
# heap[0]만 최솟값 보장
# 나머지는 정렬 X3. 동일 우선순위 처리
# 튜플로 우선순위 추가
heapq.heappush(heap, (priority, count, item))4. 배열 인덱스
# 부모: (i - 1) // 2
# 왼쪽 자식: 2 * i + 1
# 오른쪽 자식: 2 * i + 2