힙이 빛나는 곳: Top-K, 스트리밍 중앙값, 병합

"힙의 킬러 용도는 '뭔가 정렬' 이 아니야. '데이터 홍수가 있고 경계만 필요해 — 상위 몇 개, 가운데, 여러 스트림 너머 다음으로 작은 것' 이야. 전부 정렬은 절대 안 읽을 순서에 값을 치르는 거야."

Top-K: 크기-K 힙 트릭

수 십억 개 (또는 메모리에 못 담는 스트림) 가 있고 가장 큰 100 개를 원해. 정렬은 O(n log n) 이고 n 전부가 메모리에 필요해. 대신, 크기 k 최소-힙을 유지해: 각 수 push; 힙이 k 초과하면 가장 작은 걸 pop. 힙이 늘 지금까지 본 가장 큰 k 개를 들고, 그 루트가 k번째로 큰 거 — '컷오프'. 비용: O(n log k), 메모리 O(k) 뿐. k 가 n 보다 훨씬 작으면 (십억의 상위 100), 완전 정렬 대비 엄청난 승리고, 정렬이 아예 불가능한 무한 스트림에서도 작동해.

스트리밍 중앙값: 균형 잡힌 두 힙

커지는 스트림의 중앙값 유지는 어렵게 들려 — 중앙값은 가운데고, 데이터가 도착하면 가운데가 움직여. 우아한 트릭: 두 힙을 유지해. 최대-힙이 작은 절반을 들고 (그 꼭대기가 낮은 값 중 가장 큼); 최소-힙이 큰 절반을 들어 (그 꼭대기가 높은 값 중 가장 작음). 크기를 서로 하나 이내로 유지하면, 중앙값이 두 꼭대기에 딱 앉아. 각 새 값이 O(log n) 에 배치되고 재균형되고, 중앙값을 O(1) 에 읽어. 아름다운 '가운데서 만나기' 야 — 중앙값 선을 사이에 두고 마주 본 두 힙.

K 개 정렬 리스트 병합

이미 정렬된 k 개 리스트를 하나의 정렬 출력으로 병합: 각 리스트의 맨 앞 원소를 힙에 넣어 (k 항목). 가장 작은 걸 pop — 그게 병합 출력의 다음 원소 — 하고 그 리스트의 다음 원소를 push. 반복. 힙이 늘 k 후보의 현재 frontier 를 들어서, 총 N 원소 각각이 O(log k): O(N log k) 병합, 이어붙여 정렬 (O(N log N)) 보다 훨씬 나아. 정확히 외부 정렬 (메모리에 비해 데이터 너무 큼) 이랑 로그-병합이 작동하는 법이고, Python 이 heapq.merge 로 줘.

힙은 '경계' 문제를 소유해: top-k (크기-k 힙, O(n log k)), 스트리밍 중앙값 (균형 잡힌 두 힙, 항목당 O(log n)), k-way 병합 (k 앞 힙, O(N log k)). 공통 실: 순서의 가장자리만 필요하지, 전체 정렬 수열은 절대 아니야.

다 묶는 실

이것들 하나하나가 완전 정렬엔 낭비야, 각자 경계만 필요하니까: top-k 컷오프, 중앙값 선, 현재 병합 frontier. 그게 첫 lesson 힙 속성의 약속이 현금화된 거야 — 극값을 알 딱 충분한 순서만 유지하고, 그만큼만 값을 치러. 작은 정렬 조각을 읽으려고 거대 데이터셋을 정렬하려는 자신을 잡으면, 멈추고 힙이 그 조각을 훨씬 싸게 주는지 물어.

피파의 고백

난 수백만 중 트렌딩 상위 20 이 필요해서 반사적으로 sorted(items)[:20] 를 썼어 — 스무 개 읽으려고 수백만 전부 정렬. 아빠가 heapq.nlargest(20, items) 를 보여줬어, 내부에 크기-20 힙을 유지: O(n log n) 대신 O(n log 20), 안 막혔어. 재구성이 또 힙 속성이었어 — 위 가장자리만 필요한데 전체 순서를 사고 있었어. 이젠 '이거 *전부* 정렬이 필요해, 아니면 경계만?' 이 모든 정렬 전에 묻는 질문이야.

Code

Top-k, k-way 병합 (중앙값 스케치)·python

import heapq

# 크기-k 최소-힙으로 TOP-K: 스트림에서 가장 큰 k 개, O(n log k), O(k) 공간.
def top_k(stream, k):
    heap = []                          # 본 것 중 가장 큰 k 개의 최소-힙
    for x in stream:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:              # 현재 k번째로 큰 것보다 커?
            heapq.heapreplace(heap, x) # 가장 작은 거 pop, x push — O(log k) 한 번
    return sorted(heap, reverse=True)

print(top_k([7, 2, 9, 4, 1, 8, 5, 6], k=3))   # [9, 8, 7]
# 8 개 다 정렬 안 함; 가장 좋은 3 개만 유지. 십억 항목엔 이게
# '끝남' 이랑 '메모리 부족' 의 차이야.

# 힙으로 k 개 정렬 리스트 병합 (Python 이 바로 줘):
a, b, c = [1, 4, 7], [2, 5, 8], [3, 6, 9]
print(list(heapq.merge(a, b, c)))     # [1,2,3,4,5,6,7,8,9] — O(N log k)

# 스트리밍 중앙값 스케치: 최대-힙 (낮은 절반) + 최소-힙 (높은 절반),
# 균형 유지; 중앙값이 두 꼭대기에 앉음, 삽입당 O(log n).

Exercise

스트리밍 중앙값에: 왜 *작은* 절반을 최대-힙에, *큰* 절반을 최소-힙에 두는지 (각 힙의 꼭대기가 뭘 줘?), 각 삽입 후 '재균형' 이 뭘 뜻하는지 설명해. 그다음: 천만 항목의 상위 5 찾기에, 힙 접근 대 완전 정렬의 복잡도를 주고, 완전 정렬이 실제로 더 나은 선택일 때를 말해.

Hint

최대-힙 꼭대기 = 낮은 절반의 가장 큼; 최소-힙 꼭대기 = 높은 절반의 가장 작음 — 함께 중앙값을 가로질러. 재균형 = 크기가 1 넘게 다르면 한 원소를 가로질러 옮김. 상위 5: O(n log 5) vs O(n log n) — 힙 승. 근데 어차피 항목을 *완전 정렬* 해야 하면, 그냥 한 번 정렬해.

힙이 빛나는 곳: Top-K, 스트리밍 중앙값, 병합

Top-K: 크기-K 힙 트릭

스트리밍 중앙값: 균형 잡힌 두 힙

K 개 정렬 리스트 병합

다 묶는 실

피파의 고백

Code

External links

Exercise

Progress

댓글 0