Heaps
How do you keep the best k without sorting everything?
Fifty million timings, one small pod
Every morning the payments team wants one list: the 100 slowest UPI calls of the day before, so they can chase the bank behind them. Yesterday there were 50 million calls.
The script reads every timing into a Python list and sorts it. On a laptop, on a sample of one million, it finishes in two seconds. In production it is killed before it prints a line. The job runs in a pod with 1 GB of memory, and 50 million floats in a Python list need about 1.6 GB before the sort has even started. That is sorting 50 million numbers to keep 100 of them.
So keep 100. Hold the 100 slowest seen so far, and treat every new timing as a challenger. Most are fast and can be rejected at once. A few are slow enough to get in, and each time one does, somebody already on the list has to leave. The only question left is who leaves when the 101st turns up.
Pause and predict You hold the 100 slowest timings seen so far. A new one arrives. Which one value must you see instantly to decide whether it gets in?
The weakest of the k you keep
The list of 100 is one case of a general problem. You keep k values, every new value competes with them, and one of the k + 1 has to leave: the weakest, meaning the one that ranks lowest for the question. So the question you ask again and again is "which of the kept values is weakest?". A structure that answers it in O(1), and lets you replace that value in O(log k), is a heap.
A binary heap is a complete binary tree stored in an array, with one rule: every parent is less than or equal to its children. That rule is all it promises. Siblings are in no particular order, but the root is always the smallest value. Push and pop each restore the rule along one path between the root and a leaf, so they cost O(log n). Java's PriorityQueue and Python's heapq are both min-heaps.
The direction of the heap is the part people get wrong. To keep the largest values, you throw away small ones, so the smallest must be on top, and that is a min-heap. Choose the heap so that the value you will throw away is at the root.
Pause and predict n is a million and k is 100. One push or pop on the heap walks one path between the root and a leaf. About how many levels long is that path?
When the whole array is already in memory, the other classic answer is quickselect: split the array around a random pivot and continue only in the part that holds the answer, which takes O(n) time on average. It needs the whole array in memory, and with unlucky pivots it takes O(n²). The heap works on a stream, where values arrive one at a time, and 50 million timings arriving through the day are a stream.
Two heaps for a running median
Pause and predict To find the median of a stream, split the values seen so far into a lower half and an upper half. Which value of each half do you need to read instantly?
Call the max-heap low and the min-heap high. Keep two rules: every value in low is at most every value in high, and low holds the same number of values as high, or one more. When an insert breaks the size rule, move the top of the larger heap to the other heap. That top is the value of its half nearest the middle, so after the move it is still on the correct side of every value in the other heap, and the first rule still holds.
A k-way merge, and taking the best
To merge k sorted lists, notice that the smallest value of each list not yet merged is at its front. So the next value of the output is the smallest of the k front values. Keep one entry per list in a min-heap, pop the smallest, and push the next element of the same list. That is a k-way merge, and it takes O(N log k) time for N elements in total. For arrays, push (value, list number, position) so you know where the next element of that list is.
Last Stone Weight repeatedly smashes the two heaviest stones together and puts back one stone whose weight is their difference. Nothing is thrown away, and the new stone must be ranked against the rest, so keep every stone in a max-heap.
This is the shape of most schedulers. A web crawler keeps its sites in a heap keyed by the earliest time each may be fetched again, and an LLM server pops the waiting requests that should go first into each batch.
System design: the crawler's frontier LLM: batching on a GPU server
Task Scheduler: the greedy and the formula
In Task Scheduler, tasks are letters, each task takes one unit of time, and two runs of the same letter must be at least n units apart. The letter with the most copies, say m copies, limits everything: between its m runs there are m - 1 gaps of at least n units. So cut time into frames of n + 1 units, each starting with that letter. Every frame except the last is at least n + 1 units long, and the last frame holds one copy of each letter that has m copies; say there are c such letters. So the answer is at least (m - 1)(n + 1) + c. It is also at least the number of tasks, and it is exactly the larger of the two:
The heap version simulates the schedule. In each unit of time, run the letter with the most copies left among those allowed to run, then put it in a waiting queue for n units. This greedy choice is safe by an exchange argument: a letter with fewer copies left can always fill a slot later, while delaying the letter with the most copies can only push its last copy later and add idle time. Both methods give the same number. The formula is shorter, and the heap still works when the rules change.
How to recognise it
Once you see that a heap fits, decide which kind of heap from what it must throw away.
Pause and predict You want the 10 smallest values of a stream, keeping at most 10 values in a heap. Should it be a min-heap or a max-heap?
The ones that only look like it
- The maximum of each sliding window: values leave the window in the order they arrived, so a monotonic deque (a double-ended queue kept in decreasing order) does it in O(n). That is in the stack unit. A heap would have to remove values from the middle, or skip stale ones later, and costs O(n log n).
- Counting or grouping with no ranking ("does any value repeat?", "group the anagrams"): a map, in hashing. When a question asks for the k most frequent, count with a map first, then rank with a heap.
- The number of rooms needed at the busiest moment: sort the meetings by start time first. A min-heap of end times helps, but the main idea is walking through the sorted start times, which is in intervals.
- A fixed array asked about many different values of k: sort it once and read each answer by index. A heap would repeat its work for every k.
Where it bites
Pause and predict In Java, new PriorityQueue<Integer>((a, b) -> a - b) is given 2,000,000,000 and then -2,000,000,000. What does peek() return?
- The wrong direction. A max-heap that holds at most k values keeps the k smallest. Decide which value you throw away, and choose the heap that puts it on top.
- Popping at k instead of k + 1. The heap then keeps k - 1 values, and the root is the (k - 1)-th largest.
- Two heaps with the right sizes but values on the wrong side. First put the new number in the correct heap by comparing it with the top of low, then fix the sizes by moving a top across.
- Ties that compare the wrong thing. In a k-way merge, when two entries have equal values, the heap compares the next field of the tuple. Put a list index there, never a node, because two nodes cannot be compared.
- Forgetting the + c in the Task Scheduler formula, which counts the letters tied for the most copies, or forgetting that the answer is at least the number of tasks.