COMP90038 · Algorithms And Complexity
Heaps and Priority Queues
The first transform-and-conquer structure: a priority queue — an abstract type that hands you the most-urgent element on demand — implemented as a binary heap. The trick is representation: a heap is a complete binary tree stored in a plain array, so the node at index i finds its children at 2i and 2i+1 and its parent at ⌊i/2⌋ with no pointers at all. The heap property (every parent dominates its children) is restored after each change by two O(log n) routines: bubble-up (sift a new element toward the root after an insert) and bubble-down (sift the root down after a delete-min/max). Two results matter for the exam: building a heap by repeated bubble-down (heapify) is O(n), not O(n log n), because most nodes are near the bottom; and heapsort — heapify then repeatedly extract the root — sorts in-place in Θ(n log n). Q1 hand-traces an insert sequence or a heapify, so the array↔tree index arithmetic and the two sift routines have to be automatic.
What this chapter covers
- 01The priority-queue ADT and what a heap provides
- 02Array layout of a complete tree: children 2i / 2i+1, parent ⌊i/2⌋
- 03The heap property; bubble-up (insert) and bubble-down (delete) in O(log n)
- 04Bottom-up heapify in O(n) — why it beats n inserts
- 05Heapsort: heapify then extract, Θ(n log n) in place
Worked example: insert into a max-heap and bubble up
- +1Append at the next free slot. 45 goes to index 6 (the new last position): [50, 30, 40, 10, 20, 45].
- +1Bubble up: compare with parent. Parent of index 6 is index 3 = 40. Since 45 > 40, swap: [50, 30, 45, 10, 20, 40].
- +1Continue. New position index 3; parent is index 1 = 50. Since 45 < 50, stop — the heap property holds.
- +1Cost. Bubble-up made 2 comparisons, at most ⌊log₂n⌋ — insert is O(log n).
Key terms
- Priority queue
- An abstract data type supporting insert and extract-the-most-urgent (min or max). The heap implementation gives O(log n) insert and extract and O(1) peek; used by Dijkstra, Prim and Huffman, and the basis of heapsort.
- Binary heap
- A complete binary tree obeying the heap property, stored in an array so children of index i are 2i and 2i+1 and the parent is ⌊i/2⌋ — no pointers. Supports O(log n) insert/delete and O(1) find-extreme.
- Heap property
- Every parent dominates its children: ≥ in a max-heap, ≤ in a min-heap. It guarantees the extreme element sits at the root, and is the invariant that bubble-up and bubble-down restore.
- Heapify
- Build a heap from an arbitrary array by bubble-down on every internal node from the last up to the root. It runs in O(n) — not O(n log n) — because most nodes are shallow, so their sift distance is small.
- Heapsort
- Sort by heapify-then-repeatedly-extract-the-root, swapping each extracted maximum to the end of the array. Θ(n log n) in all cases and in-place, though not stable.
Heaps and Priority Queues FAQ
Why is a heap stored in an array instead of with nodes and pointers?
Because a heap is always a complete tree, its shape is fixed, so the array index encodes the tree structure: child = 2i / 2i+1, parent = ⌊i/2⌋. That removes all pointer overhead, gives cache-friendly contiguous storage, and makes the index arithmetic the whole of the implementation.
Why is heapify O(n) when it does n bubble-downs?
Because the bubble-down cost depends on a node's height, and most nodes are near the bottom with height 0 or 1. Summing height×count over all levels gives a series that converges to O(n), not O(n log n). Building by n successive inserts, by contrast, really is O(n log n).
What is the difference between heapsort and a priority-queue sort?
They are the same idea: heapsort heapifies the array in place and repeatedly extracts the max to the end, which is exactly “insert all, then extract all” from a heap-backed priority queue — but done in the array itself, so it uses O(1) extra space and runs in Θ(n log n).
Exam move
Drill the array↔tree index arithmetic and the two sift routines until they are automatic, because Q1 hand-traces an insert sequence, a delete-min, or a full heapify on a small array and each is a one-mark trace where order matters. Be ready to justify two facts in a Q2 answer: heapify is O(n) (the height-weighted sum), and heapsort is Θ(n log n) in place. Recognise “repeatedly need the smallest/largest” as the priority-queue cue that later powers Dijkstra, Prim and Huffman.
