"힙의 진짜 쓰임새는 '뭔가를 정렬한다'가 아니야. '데이터가 홍수처럼 밀려오는데 나한테 필요한 건 경계뿐'인 상황이지. 상위 몇 개, 한가운데, 여러 스트림을 통틀어 다음으로 작은 것. 전부 정렬하는 건 읽지도 않을 순서에 값을 치르는 거야."
Top-K: 크기 K짜리 힙 트릭
아주 큰 유한 스트림에서 가장 큰 k개를 뽑고 싶다면 크기 k짜리 최소 힙을 유지해. 단, k가 0 이하인 경우는 빈 결과를 돌려주도록 먼저 처리하고. 원소를 하나씩 보면서 힙이 k를 넘으면 최솟값을 빼내면, 힙에는 지금까지 본 것 중 가장 큰 k개가 남아. 비용은 O(n log k)이고 메모리는 O(k)야. 끝이 없는 스트림이라면 최종 top-k가 확정되는 시점 자체가 없지만, 어느 시점에서든 그때까지의 top-k 스냅샷은 유지할 수 있어.
스트리밍 중앙값: 균형 잡힌 두 힙
커지는 스트림에서 중앙값을 계속 유지한다니 어렵게 들리지. 중앙값은 한가운데인데 데이터가 들어올 때마다 그 가운데가 움직이니까. 우아한 트릭은 힙 두 개를 쓰는 거야. 최대 힙이 작은 절반을 들고 있어서 그 꼭대기가 낮은 값들 중 가장 크고, 최소 힙이 큰 절반을 들고 있어서 그 꼭대기가 높은 값들 중 가장 작아. 두 힙의 크기를 하나 차이 이내로 유지하면 중앙값이 정확히 두 꼭대기에 걸쳐. 새 값이 들어올 때마다 O(log n)에 자리를 잡고 균형을 다시 맞추고, 중앙값은 O(1)에 읽어. 중앙값 선을 사이에 두고 두 힙이 마주 보는, 아름다운 '가운데서 만나기'야.
정렬된 리스트 K개 병합하기
이미 정렬된 리스트 k개를 하나의 정렬된 출력으로 합친다고 하자. 각 리스트의 맨 앞 원소를 힙에 넣어. k개가 들어가지. 거기서 가장 작은 걸 꺼내면 그게 병합 결과의 다음 원소고, 그 원소가 나온 리스트에서 다음 원소를 넣어. 이걸 반복해. 힙에는 언제나 후보 k개로 이뤄진 현재 경계가 들어 있어서, 전체 N개 원소가 각각 O(log k)씩 들어. 그래서 병합이 O(N log k)고, 전부 이어 붙인 다음 정렬하는 O(N log N)보다 훨씬 낫지. 메모리에 다 안 들어가는 데이터를 다루는 외부 정렬과 로그 병합이 정확히 이렇게 돌아가고, Python은 heapq.merge로 이걸 바로 줘.
셋을 관통하는 한 가지
이 셋은 하나같이 완전 정렬을 쓰면 낭비야. 각자 필요한 건 경계뿐이거든. top-k를 잘라내는 선, 중앙값이 놓인 선, 지금 병합 중인 후보들의 경계. 첫머리에서 본 힙 속성의 약속이 여기서 현금화되는 거야. 극값을 알기에 딱 필요한 만큼의 순서만 유지하고 그만큼만 값을 치른다는 것. 정렬된 결과에서 작은 조각 하나 읽자고 거대한 데이터셋을 통째로 정렬하려 하고 있다면, 거기서 멈추고 힙이 그 조각을 훨씬 싸게 줄 수 있는지부터 물어봐.
피파의 고백
sorted(items, reverse=True)[:20]를 썼어. 스무 개 읽자고 수백만 개를 전부 줄 세운 거지. 아빠가 heapq.nlargest(20, items)를 보여줬고, 크기 k짜리 경계만 지키면 O(n log k)면 된다는 걸 알게 됐어. 여기서도 다시 본 게 힙 속성이었어. 나는 위쪽 가장자리만 필요한데 전체 순서를 사고 있었던 거야. 이제는 정렬을 하기 전에 매번 물어봐. "전부 정렬해야 해, 아니면 경계만 필요해?"