A priority queue is not a sorted array
A min-priority queue holds a multiset of comparable keys. It supports insertion and removal of one minimum key; asking to remove from an empty queue reports underflow. Equal keys are allowed. A binary min-heap supplies these operations without keeping the entire array sorted, and it does not by itself promise first-in-first-out order among equal keys.
Definition 3.1.1
(Binary min-heap)
Use one-based positions in a contiguous array. For , its parent is ; its possible children are and when those indices do not exceed . The array is a min-heap when the heap invariant holds:
The index rules make the shape a complete binary tree: levels are filled from left to right. Following parent links from any index reaches , and the invariant shows that is a minimum when . The array need not be increasing: is a min-heap although .
Concept lensStructural
Positions as binary strings
Write each position in binary. Position is the root; the children of position are and , that is, the binary string of followed by or by . The parent deletes the last bit. For example has parent and depth . The depth of position is the number of bits minus one, and every position at depth is at least . This description of the same tree explains both the complete shape and the logarithmic height used below.
We assume constant-time key comparison and array access. The bounds below count comparisons and moves with enough allocated capacity; a resizing array may occasionally copy all elements, so its separate allocation cost needs its own analysis.
Insert: repair the path upward
Append the new key at position , then repeatedly compare it with its parent. If it is strictly smaller, swap them and continue from the parent; otherwise stop. Equality needs no swap.
Theorem 3.1.2
(Insertion preserves the heap invariant)
Let be a min-heap and let be a key. Appending and moving it up while it is strictly smaller than its parent produces a min-heap holding the old keys together with .
Proof
(A loop invariant along the upward path)
Let be the position currently holding . We claim: (i) every parent-child edge not ending at satisfies the invariant, and (ii) if has a parent , then for every child of . Initially is a leaf, so (ii) is empty, and every old edge is ordered.
If , or , the loop stops and the only possibly bad edge, the one ending at , is ordered, so the array is a heap. Otherwise , and we swap. The new edge is ordered because . For a child of , by (ii), so the edge is ordered. For the sibling of , by the old edge , so the edge is ordered. Finally, now sits at . Let be the parent of , if any. The old edge gives , and , so is at most both children of , which is (ii) at ; only the edge ending at can still be wrong. The position decreases at each step, so the loop ends. Swaps preserve the multiset and the append preserves the complete shape.
Worked example 3.1.3
(Inserting 1 into a six-element heap)
Insert into . Append at position , swap with , then with :
The key stops at the root, position . The multiset is the old one plus .
Remove a minimum: repair the path downward
For , return the sole element and leave an empty array. For , save and return the root, move the last key into position , and shorten the array by one. Then, while the current node has a child smaller than its key, swap with a smaller child; if two children tie, choose either. Continue at that child's former position. Stop at a leaf or when the key is no larger than either existing child.
Theorem 3.1.4
(Removing a minimum)
Let be a min-heap with . The procedure above returns a minimum key and leaves a min-heap holding the remaining keys.
Proof
(A loop invariant along the downward path)
The returned root is a minimum, because for all by the invariant. After the last key is moved to position , both child subtrees of the root are still heaps. Let be the position holding . We claim: (i) every edge not leaving is ordered, and (ii) if has a parent , then for each child of . Initially , so (ii) is empty.
If no child of is smaller than , the edges leaving are ordered and the array is a heap. Otherwise let be a smaller child of , so and for the other child . After the swap, the edge is ordered since by (ii); is ordered since ; and is ordered since . The children of satisfy in the old array, which says that the new value at is at most , so (ii) holds at and only edges leaving can be wrong. The position moves down a level each step, so the loop ends at a leaf or by the stopping test. Removing the last position preserves the complete shape.
Proof X-ray
Why the smaller child must be chosen
The key move is the choice of the smaller child . It is used in exactly one inequality of the proof: makes the edge to the sibling ordered after the swap. Everything else holds for either child. Condition (ii) is what makes the edge above safe: the new value comes from below , so it is at least . The loop terminates because the position strictly increases, and it closes when the moved key meets a leaf or no child is smaller. The tie case needs no special care, since either child satisfies .
Counterexample mode
Swapping with the larger child
Claim: while deleting, it is enough to swap the moved key with any child that is smaller than it. Take the heap and remove the minimum. The last key moves to the root, giving , and both children are smaller than . Swapping with the larger child gives . Position is a leaf, so the loop stops, yet the root exceeds its child : the result is not a heap. Swapping with the smaller child gives ; position has no children, and , , so this is a heap. The rule must name the smaller child, so that the key moving up is below its sibling.
Worked example 3.1.5
(Removing the minimum after that insertion)
Removing the minimum from returns and moves the last key to the root, giving . The smaller child is , and one swap gives . The key is now at position , whose only child is larger, so the loop stops.
Height and operation costs
Theorem 3.1.6
(Logarithmic height and cost)
A heap with elements has height at most . Insertion into it makes at most swaps. Removal makes at most swaps, and visits at most positions, with at most two key comparisons at each.
Proof
(Counting levels)
At depth , every index is at least , as the binary-string description shows. An index is at most , so and . Insertion starts at position , of depth at most , and moves up one level per swap. Removal for works on elements, whose height is at most ; it starts at the root and moves down one level per swap. At each visited position it compares the two children with each other and the smaller one with the key. The active array uses space.
With denoting the size before the operation, each operation therefore costs under the allocation assumption above. Reading a minimum without removing it takes for a nonempty heap. These are bounds for these operations, not a proof of a particular bulk-construction method or stable priority order.
Worked example 3.1.7
(Ties and the one-element heap)
Remove a minimum from . Save , move the last key to the root and shorten the array: . The root has a smaller child , so swap to get , a heap. Next insert into : append at position to get ; its parent at position holds , and the new key is not strictly smaller, so no swap occurs. At the edge case , removal returns the sole key and leaves the empty array; on the empty array it reports underflow.
Common mistake
(Reading the second smallest key at position 2)
Only is known to be a minimum. In the heap , position holds , but the second smallest key is , at position . The invariant orders each key against its parent only, so the two children of the root are not ordered with each other.
Common mistake
(Using one-based child formulas with zero-based arrays)
With zero-based positions, the children of are and . Using and there makes position its own child, and position would have children and , not the correct and . Fix one convention and derive the parent and children formulas from it.
Exercises with solutions
Quick check
(Check an invariant. Is a min-heap?)
Compare every position with its parent.
Solution · Answer
No: position has key , greater than its child at position with key .
Quick check
(Ties. Can be a min-heap?)
Which comparisons does the invariant require?
Solution · Answer
Yes. Both parent-child comparisons are non-strict; either copy of the minimum may be removed first.
Quick check
(Deletion. Delete a minimum from using the stated algorithm.)
Move the last key to the root first.
Solution · Answer
Move to the root to get ; swap with smaller child to obtain .
Quick check
(Underflow. What should removal from the empty heap do?)
Is there a root key to return?
Solution · Answer
Report underflow; there is no root key to return. The one-element case returns its key and leaves the heap empty.