Ch.11 고급 자료구조
Heap 심화 — heapify부터 Two Heaps까지
배열을 힙으로 만드는 데 O(n log n)이 아니라 O(n)?
100만 개의 숫자가 들어오는 스트림에서 '지금까지의 중간값'을 실시간으로 알려야 합니다. 정렬하면 O(n log n), 하지만 Two Heaps를 쓰면 O(log n)에 가능합니다.
힙 하나로는 중간값을 구할 수 없다 — 어떻게 두 개를 조합할까?
heapify의 O(n) 비밀부터 시작하여, heap sort, 그리고 Two Heaps 패턴까지 마스터합니다.
핵심 개념
heapify
임의의 배열을 heap 조건을 만족하도록 재배치하는 연산
sift-down
부모를 자식과 비교하며 아래로 내리는 연산
핵심 내용
n개 원소를 하나씩 insert하면 O(n log n). 하지만 heapify는 O(n)에 완성합니다
핵심 아이디어: 아래에서 위로 sift-down. 리프 노드(절반)는 이미 힙이므로 건너뜁니다
def heapify(arr):
n = len(arr)
# 마지막 부모부터 루트까지 sift-down
for i in range(n // 2 - 1, -1, -1):
sift_down(arr, n, i)
def sift_down(arr, n, i):
largest = i
left, right = 2 * i + 1, 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
sift_down(arr, n, largest)왜 O(n)인가? • 높이 h인 노드 수: n/2^(h+1) • 각 노드의 sift-down 비용: O(h) • 총합: Σ(h=0→log n) n/2^(h+1) × h = O(n) • 리프(절반)는 sift-down 불필요 → 대부분 비용이 낮음
Heap Sort는 두 단계입니다: 1) heapify O(n) 2) 추출 반복 O(n log n)
def heap_sort(arr):
n = len(arr)
# 1단계: max-heap 구성 — O(n)
heapify(arr)
# 2단계: 최대값을 끝으로 보내고 힙 크기 축소
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # 최대값 → 끝
sift_down(arr, i, 0) # 힙 복원면접 팁: Heap Sort의 장점은 in-place O(n log n). 단점은 불안정 + 캐시 비친화적
언제 Heap을 쓰고, 언제 BST를 써야 할까요?
Heap: 최솟값/최댓값만 빠르게 → O(1) peek, O(log n) push/pop BST: 임의 원소 검색, 정렬 순회 → O(log n) search/insert Top-K, 중간값 → Heap | 범위 검색, 순서 통계 → BST
숫자가 하나씩 들어올 때 지금까지의 중간값을 O(log n)에 구합니다
아이디어: 작은 절반은 max-heap, 큰 절반은 min-heap. 중간값은 항상 두 힙의 루트 사이에 있습니다
import heapq
class MedianFinder:
def __init__(self):
self.lo = [] # max-heap (부호 반전)
self.hi = [] # min-heap
def addNum(self, num: int) -> None:
heapq.heappush(self.lo, -num)
# lo의 최대값을 hi로 이동
heapq.heappush(self.hi, -heapq.heappop(self.lo))
# 크기 균형: lo >= hi
if len(self.lo) < len(self.hi):
heapq.heappush(self.lo, -heapq.heappop(self.hi))
def findMedian(self) -> float:
if len(self.lo) > len(self.hi):
return -self.lo[0]
return (-self.lo[0] + self.hi[0]) / 2addNum: O(log n) — heappush 2~3번 findMedian: O(1) — 루트만 확인 공간: O(n) — 모든 원소 저장
숫자 [5, 2, 8, 1]을 하나씩 추가하며 추적합니다
lo의 최대값(-lo[0])과 hi의 최소값(hi[0]) 사이에 중간값이 항상 존재!
면접에서 Heap 관련 자주 나오는 질문들을 정리합니다
Python 면접에서는 heapq 모듈 사용법을 반드시 숙지하세요. nlargest, nsmallest도 유용!
heapify의 시간 복잡도는?
Two Heaps에서 max-heap에는 어떤 원소들이 들어가나요?
Heap Sort는 안정 정렬이다
핵심 용어
heapify
배열 → 힙 변환, sift-down 방식으로 O(n)
sift-down
부모를 자식과 비교하며 아래로 내리는 연산
Two Heaps
max-heap + min-heap으로 중간값을 실시간 추적
시간
O(n log n) — heapify O(n) + 추출 O(n log n)
공간
O(1) — in-place 정렬
안정성
불안정 정렬 (같은 값의 순서 보장 X)
heapify가 O(n)인 이유?
리프는 건너뛰고, 상위 노드일수록 적으므로
Python heapq는?
min-heap만 지원. max-heap은 부호 반전
Heap Sort vs Quick Sort?
Heap은 최악 O(n log n), Quick은 평균 O(n log n)이지만 캐시 효율적
시각 자료
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작