"힙은 작은 동작 둘로 자기를 유지해: 너무 작은 원소를 루트 쪽으로 띄우거나, 너무 큰 걸 리프 쪽으로 가라앉혀. 모든 힙 연산이 그 둘 중 하나를 O(log n) 번 반복한 거야."
Push: 끝에 추가, 그다음 위로 sift
힙에 삽입하려면: 새 값을 배열 끝 (다음 리프, 완전성 보존) 에 떨구고, 위로 sift 해 — 부모보다 작은 동안 swap 하며 루트 쪽으로 올라. 더 이상 부모보다 작지 않으면 (또는 꼭대기 닿으면) 멈춰. 오름이 많아야 트리 높이라, push 는 O(log n). 단일 루트-리프 경로를 따라 힙 속성을 회복하지, 힙 나머지는 안 건드려.
Pop: swap, 줄이기, 아래로 sift
최솟값 (늘 루트) 제거하려면: 루트 저장, 마지막 원소를 루트 자리로 옮기고, 배열을 하나 줄이고, 아래로 sift 해 — 더 작은 자식보다 큰 동안 그 자식이랑 swap 하며 리프 쪽으로 가라앉아. 또 많아야 트리 높이라, pop 은 O(log n). 제거 없이 최소 엿보기는 O(1) (그냥 인덱스 0 읽기). push 랑 pop 은 거울상이야: 하나는 위로 띄우고, 하나는 아래로 가라앉히고, 둘 다 단일 경로를 고쳐.
Push = 끝에 추가 + 위로 sift (O(log n)). Pop = 루트 가져오고, 마지막 원소를 올리고, + 아래로 sift (O(log n)). Peek = 인덱스 0 읽기 (O(1)). 모든 힙 연산이 한 루트-리프 경로를 따라 순서를 회복해.
놀람: 힙 짓기는 O(n log n) 이 아니라 O(n)
순서 없는 배열이 있고 힙으로 바꾸고 싶다고 해. 당연한 방식 — 원소를 하나씩 push — 은 O(n log n). 근데 아름다운 더 빠른 방법이 있어: 마지막 부모에서 시작해 루트로 거슬러 가며 모든 노드를 아래로 sift. 이게 O(n) 에 유효한 힙을 지어 — 선형로그가 아니라 선형. 왜인지 직관: 대부분 노드가 바닥 근처고 (리프가 트리 절반) 아주 작은 sift-down 거리야; 루트 근처 몇 노드만 멀리 sift 해. 그 거리들을 합하면 O(n log n) 이 아니라 O(n). 진짜 놀라운 결과고, 일을 하는 순서가 복잡도를 바꿀 수 있다는 사랑스러운 예야. (Python 의 heapq.heapify 가 정확히 이걸 써.)
피파의 고백
난 힙 짓기가 O(n log n) 일 수밖에 없다고 확신했어 — n 삽입, 각 O(log n), 당연하잖아. 아빠가 상향식 sift-down 이랑 O(n) 증명을 보여줬고, 합산이 날 설득하기 전까지 10분을 다퉜어. 박힌 교훈: 내 '당연한' 복잡도는 모든 노드의 최악 케이스를 세고 있었어, 대부분 노드가 거의 안 움직이는 리프인데. 비용 분석은 모든 단계가 비싼 거라 가정하는 게 아니라 일의 분포를 보는 걸 보상해.
Code
Push, pop, 그리고 O(n) build-heap·python
def sift_up(heap, i):
while i > 0:
p = (i - 1) // 2
if heap[i] < heap[p]: # 부모보다 작아? 올라가
heap[i], heap[p] = heap[p], heap[i]
i = p
else:
break
def push(heap, value): # O(log n)
heap.append(value) # 끝에 추가 (다음 리프)
sift_up(heap, len(heap) - 1)
def sift_down(heap, i):
n = len(heap)
while True:
l, r, smallest = 2*i+1, 2*i+2, i
if l < n and heap[l] < heap[smallest]: smallest = l
if r < n and heap[r] < heap[smallest]: smallest = r
if smallest == i: break
heap[i], heap[smallest] = heap[smallest], heap[i]
i = smallest
def pop_min(heap): # O(log n)
heap[0], heap[-1] = heap[-1], heap[0] # 루트랑 마지막 swap
m = heap.pop() # 끝에서 옛 루트 제거
if heap: sift_down(heap, 0)
return m
def build_heap(arr): # O(n) — 놀람!
for i in range(len(arr)//2 - 1, -1, -1): # 마지막 부모 -> 루트
sift_down(arr, i)
return arr
h = []
for x in [5, 3, 8, 1, 9, 2]: push(h, x)
print("pops:", [pop_min(h) for _ in range(6)]) # [1, 2, 3, 5, 8, 9] 정렬됨!
print("O(n) build:", build_heap([5, 3, 8, 1, 9, 2])) # 유효한 힙, 루트=최소