Heaps: top-K, two heaps, k-way merge
Keep a heap of exactly the items you still care about. Its root is the smallest of them, free to read, and one log-time push and pop keeps the collection right as it changes.
Problems worked on this page, and more to practise
- 215. Kth Largest Element in an Array
- 23. Merge k Sorted Lists
- 295. Find Median from Data Stream
- 1046. Last Stone Weight
- 703. Kth Largest Element in a Stream
- 347. Top K Frequent Elements
- 973. K Closest Points to Origin
- 621. Task Scheduler
- 767. Reorganize String
- 253. Meeting Rooms II
- 378. Kth Smallest Element in a Sorted Matrix
- 373. Find K Pairs with Smallest Sums
- 502. IPO
When should I use a heap instead of sorting?
Sort when you need the whole order once and the collection does not change. Use a heap when the collection keeps changing and you only ever need the extreme item: sorting costs O(n log n) and has to be redone after every change, while a heap answers in O(1) and absorbs a change in O(log n). For a top-K question over n items a heap of size k is O(n log k) time and O(k) space, and it works on a stream you cannot hold in memory.
Why does keeping the k largest items need a min-heap?
Because the item you throw away is the smallest of the ones you are holding, and a min-heap puts exactly that item at the root. Push every number, and whenever the heap holds more than k, pop the root. The number that leaves is the smallest of the k + 1 candidates, so it cannot be in the top k of anything you have seen. When the scan ends, the root of the heap is the k-th largest.
How do I make a max-heap in Python?
You negate. heapq only ever gives you the smallest item, so push -x instead of x and negate again on every read, including the value you return. For tuples, negate only the component you are ordering by and keep the rest positive, as in (-count, word). heapq.nlargest(k, xs) is the other route and needs no negation at all, which is often the better answer when you are not inside a loop.
Why does my heap raise a TypeError only on some inputs?
A tuple comparison walks left to right. While the first elements differ, the second elements are never compared, so a heap of (priority, object) pairs works until two priorities tie. On a tie Python compares the objects, and a plain object has no order, so it raises. The fix the heapq documentation recommends is a counter between the priority and the payload: no two counters are equal, so the payload is never compared, and ties come out in arrival order.
Is a heap sorted?
No. The only rule is that each item is no larger than its two children, at indices 2i + 1 and 2i + 2 of the backing list. That fixes the smallest item at index 0 and says nothing at all about two items in different branches, which is why a heap cannot answer “is x in here” or “what is the third smallest” without taking the heap apart. Printing the list of a heap and expecting sorted output is the first surprise everyone gets.