Data structures · intermediate
Heap and priority queue
A priority queue removes the highest-priority item rather than the oldest; a binary heap commonly implements it as a complete tree where every parent outranks its children.
Why it matters
Heaps provide efficient repeated access to the current minimum or maximum without fully sorting all remaining items.
Mental model
How to reason about heap and priority queue
The root is globally best, but siblings and separate subtrees are not fully ordered. Insert bubbles upward and removal repairs the root by sifting downward, each across at most the tree height.
Analogy
An emergency waiting room always knows the most urgent patient, but it does not keep every patient in a complete first-to-last ranking.
Examples
See the boundary, not just the happy path
Worked example · Select the next deadline
push(deadline, job); next = popMin()Insertion and minimum removal each cost O(log n), while inspecting the minimum costs O(1).
Worked example · Keep the largest k
maintain a min-heap of at most k scoresThe root is the smallest retained score, so a better candidate can replace it in O(log k) time without sorting all inputs.
Useful contrast · Not globally sorted
min-heap array: [1, 4, 2, 9, 7, 3]Every parent is no larger than its children, yet array order and sibling order are not sorted.
Common mistakes
Misconceptions to remove early
Searching arbitrary values as if the heap were a BST
The heap invariant identifies the best root but cannot choose a single subtree for an arbitrary key; search may require Theta(n).
Changing priority behind the heap's back
Mutating a stored priority can violate the invariant. Use a supported decrease-key operation, reinsert, or an invalidation strategy.
Quick check
Can you predict the result?
1. What does a min-heap guarantee about its root?
- • It is a minimum element
- • Every array position is globally sorted
- • It is the most recently inserted element
2. Why can a heap return minima efficiently without maintaining a fully sorted sequence?
Keep building