IntermediateHeap / Priority Queue
Top K with a small heap
For the k largest, keep a min-heap of size k. Its top is the smallest of your best k, the one to kick out. O(n log k).
The idea
Sorting everything to take the top k costs O(n log n). A min-heap that never grows past k does better: push each number, and if the heap has more than k, pop the smallest. What's left are the k largest.
The heap's top is then the k-th largest overall.
Worked example
k = 2 on [3, 2, 1, 5, 6, 4]
- push 3, 2 → [2, 3]
- push 1 → pop 1 → [2, 3]; push 5 → pop 2 → [3, 5]; push 6 → pop 3 → [5, 6]; push 4 → pop 4 → [5, 6]
- 2nd largest = top = 5
In code (Python)
import heapq
def kth_largest(nums, k):
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap) # drop the smallest
return heap[0]
# Python has a max-heap only via negation:
# heapq.heappush(h, -x); largest = -h[0]O(n log k) time, O(k) space.
How to spot it
- “k largest / smallest / closest / most frequent”, “k-th largest”, streams of data.
Common mistakes
- Using a max-heap of everything (O(n log n), O(n) space).
- Forgetting Python's heapq is a min-heap.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →