Practice: Kth Largest Element
A heap of size k.
Find the K th largest number in a list. For example, the third largest. Sorting works, but it's O of N log N, and sorts far more than we need. Pause. Which structure keeps track of the biggest few numbers?

- The kth largest number
- Sorting does too much
- Which structure helps?
A min heap of size k
We keep a min heap holding the K largest numbers seen so far. Each new number is pushed in, and if the heap grows past K, we pop the smallest. So the top of the heap is always the K th largest. Run it. The third largest is eight.
import heapq
def kth_largest(nums, k):
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]
print(kth_largest([3, 9, 1, 8, 4, 10, 2, 7], 3))8
Costs
Each push and pop costs O of log K, so the whole thing is O of N log K. When K is small, that's much faster than sorting. It also works on a stream of numbers that never ends, because we only ever keep K of them. Python's heap Q dot N largest uses this same idea.
| key | value |
|---|---|
| Heap size | k |
| Each step | O(log k) |
| Total | O(n log k) |
| Shortcut | heapq.nlargest(k, nums) |
Summary
Keep a min heap of the K largest numbers, and its top is the answer. Next, binary search on a rotated list.
Key takeaways- Min heap of size k
- Pop when too big
- Top is the answer