Lesson 18.1 · Heaps and Priority Queues
How a Heap Works Inside an Array
A min-heap is a complete binary tree where every parent is ≤ its children, stored in an array: the children of index i are 2i + 1 and 2i + 2.
15 min
Think of it like this
A hospital emergency room: patients aren't served in arrival order but by urgency. A new patient may move ahead of some, but only compared with the people on their path up the line, not with everyone.
1.The shape and the rule
Shape: a complete binary tree, filled level by level, left to right. That's why it fits in an array with no gaps: the parent of index i is (i − 1) / 2, its children are 2i + 1 and 2i + 2.
Rule (min-heap): every parent is ≤ its children, so the minimum is always at index 0. Siblings aren't ordered with each other, so a heap is not sorted.
2.Insert: sift up
Append the new value at the end (keeping the shape), then swap it with its parent while it's smaller. At most one swap per level: O(log n).
heap = [1, 3, 5, 7, 4], add 2Step 1/4A valid min-heap: every parent ≤ its children.
3.Remove the top: sift down
Take the root. Move the last element to the root, then swap it with its smaller child while it's larger than that child. O(log n).
Building a heap from n items with new PriorityQueue<>(collection) uses bottom-up heapify, which is O(n), cheaper than n separate inserts.
heap = [1, 3, 2, 7, 4, 5]Step 1/4The answer is the root, 1.
Remember
- Parent (i − 1) / 2, children 2i + 1 and 2i + 2.
- offer and poll are O(log n), peek is O(1).
- A heap is not sorted; only the top is known.
Common mistakes
- Expecting iteration over a PriorityQueue to be in sorted order.
- Using remove(Object) in a loop: it's O(n) each time.
Words used in this lesson
- Heap
- A complete binary tree where each parent is ≤ (min-heap) or ≥ (max-heap) its children.
- Complete tree
- Every level full except possibly the last, which fills from the left.
- Sift up / down
- Swapping an element with its parent or child until the heap rule holds again.