What is a Heap?
A heap is a tree-shaped structure that keeps one extreme value at the root. A min-heap keeps the smallest value there, while a max-heap keeps the largest.
You need arrays, binary trees, and index arithmetic. The short version is: use a heap when you need one current extreme repeatedly but do not need the whole collection sorted.
The Core Idea: Keep the Cutoff
In LC 215: Kth Largest (k=2), the values are [3,2,1,5,6,4].
We keep a min-heap containing only the two largest values seen so far.
Why a min-heap for a largest-value problem? The root is the smaller of the two kept candidates. Any new value must beat that root to enter the top two.
It is like a two-seat final round in a competition. The weaker finalist is always the one a new challenger must beat.
How a Size-k Heap Filters Values
The Rule You Keep True
In a min-heap, every parent is less than or equal to its children.
For kth largest, the heap also contains exactly the largest k values from the processed prefix once at least k values have been read.
Heap size changes the purpose:
- Size
kmin-heap keeps the largestkvalues. - Size
kmax-heap keeps the smallestkvalues. - Unbounded priority queue always returns the next item by priority.
- Two heaps split a stream around its median.
Find Median from Data Stream is the one that usually trips us up. One heap stores the lower half and the other stores the upper half. Both their ordering and their size difference must remain valid after every insertion.
Picking the Right Shape
From Rule to Code
- Decide which extreme value the root must represent.
- Insert the next candidate at the end of the heap array.
- Move it upward while it violates the parent rule.
- Remove or replace the root when the heap exceeds its allowed size.
- Move the replacement downward until heap order returns.
Keeping k candidates processes n values in O(n log k) time and uses O(k) extra space.
When to use it
- •You repeatedly need the smallest or largest item from a changing collection.
- •The problem asks for the top `k`, kth largest, or next highest-priority item.
- •Keeping every item fully sorted would do more work than the question requires.
- •Items arrive over time and the current best candidates must stay available.
How to identify it
- •Words such as top, kth, smallest, largest, median, or priority appear.
- •Only one extreme item needs to be removed or inspected at each step.
- •The collection changes between queries.
- •A bounded group of the best `k` candidates is enough.
Key insights
- →A heap guarantees that its root is an extreme value, not that every item is fully sorted.
- →A min-heap of size `k` keeps the `k` largest values because its root is the weakest kept candidate.
- →Insertion and removal restore heap order by moving along one root-to-leaf path.
- →The comparison rule determines whether the heap is a min-heap or max-heap.
- →A heap is useful when priorities change less often than the extreme item is requested.
Common mistakes
- 01Expecting iteration over a heap array to produce fully sorted order.
- 02Using a max-heap when the root must represent the cutoff among the largest `k` values.
- 03Removing the root without restoring the heap property.
- 04Keeping all `n` values when only `k` candidates are needed.
- 05Ignoring how duplicate values affect rank but not heap validity.