Lesson 09 of 16 · 24:08
Heaps & priority queues
A heap is a partial ordering designed to expose one extreme value quickly. In a min-heap, every parent is no larger than its children, so the minimum is at the root. The rest is not globally sorted, which is exactly why a heap can update more cheaply than maintaining full order.
Heap questions usually involve repeated access to the smallest or largest item, top k elements, or scheduling by priority. Decide which extreme you need and what each heap entry must contain before reaching for the data structure.
What you should be able to do after this lesson
- Distinguish heap order from sorted order
- Trace sift-up and sift-down
- Choose heap size based on the k items that matter
The mental model
A heap guarantees only that each parent outranks its children. That is enough to expose the minimum or maximum without fully sorting everything.
Recognize it when: Use a heap for repeated min/max extraction, top-k, streaming selection, scheduling, k-way merge, or whenever full ordering would do unnecessary work.
The invariant to say aloud: The array represents a complete tree and every parent satisfies the heap-order relation with its children.
Learn the ideas one at a time
Concept 1 of 5
Complete tree in an array
Watch from 0:00 ↗For zero-based index i, children are 2i+1 and 2i+2; parent is (i-1)//2. Completeness keeps height O(log n).
A heap's shape is always complete, so an array stores it without pointers or interior gaps. Parent and child indices are arithmetic. Completeness also keeps height logarithmic, which bounds the number of swaps needed to repair the heap.
Walk through an example
At index 2, children are indices 5 and 6 and the parent is index 0. The array layout represents tree shape; it does not mean neighboring array values are sorted.
In an interview
Separate the shape invariant—complete tree—from the order invariant—parent dominates children. Both are required.
Concept 2 of 5
Push and pop
Watch from 0:00 ↗Push appends then sifts up. Pop swaps in the last value then sifts down. Both repair one root-to-leaf path in O(log n).
Push places a value in the next open leaf position and sifts it upward while it violates the parent relation. Pop removes the root, moves the last leaf to the root, and sifts it downward toward the better child. Only one root-to-leaf path needs repair.
Walk through an example
Push 2 into min-heap [3,5,4]. Append to get [3,5,4,2], swap with 5, then swap with 3, producing [2,3,4,5].
In an interview
Describe why O(log n) follows from tree height, and remember that peeking at the root is O(1).
Concept 3 of 5
Heapify
Watch from 0:00 ↗Bottom-up heapify repairs internal nodes from the last parent to the root. Despite individual O(log n) bounds, the aggregate work is O(n).
Bottom-up heapify starts at the last internal node because leaves are already valid one-node heaps. Sifting each internal node downward looks like O(n log n), but most nodes are near the leaves and move very little, so the summed work is O(n).
Walk through an example
Process parents from floor(n/2)-1 back to 0. After repairing index i, both child subtrees are already heaps, so one sift-down makes the subtree rooted at i a heap.
In an interview
Know the distinction: n individual pushes cost O(n log n), while bottom-up heapify of all n items costs O(n).
Concept 4 of 5
Priority queue
Watch from 0:00 ↗The priority determines removal order. Python heapq is a min-heap; store tuples for tie-breaking and negated priorities when a max-heap simulation is appropriate.
A priority queue is the interface—insert an item and remove the highest-priority item—while a heap is the common implementation. Python's heapq is a min-heap. Tuples compare lexicographically, so include a stable counter when equal priorities would otherwise compare non-orderable payloads.
Walk through an example
Entries (priority, sequence, task) make smaller priority leave first and sequence break ties. Negating numeric priorities simulates maximum-first behavior when that convention is clear.
In an interview
Define what priority means and whether stale entries can remain. Some shortest-path implementations push improved distances and skip stale pops.
Concept 5 of 5
Heap sort
Watch from 0:00 ↗Heapify, then repeatedly extract the extreme. It achieves O(n log n), but ordinary application code often uses a tuned built-in sort instead.
Heap sort first builds a heap, then repeatedly moves the extreme to its final array position and repairs the reduced heap. It guarantees O(n log n) time and can be in-place, but it is not stable and often has worse practical locality than tuned library sorts.
Walk through an example
A max-heap places the largest value at index 0. Swap it with the final active slot, shrink the active heap, and sift the new root down; the sorted suffix grows from the right.
In an interview
Use a heap for repeated extremes or top k. Use the language's built-in sort when the entire output must simply be ordered unless constraints suggest otherwise.
Before you call this lesson done
- Name min-heap or max-heap
- Define each entry and tie-breaker
- Keep only k items when appropriate
- Use O(n) heapify when starting from all data
