COMP5112 Chap.7 Heaps and Priority Queues
Heaps and Priority Queues
Complete shape enables index arithmetic
A max-heap combines a complete binary-tree shape with the rule that each parent is at least as large as its children. Level-order array storage turns child and parent links into arithmetic.
The chapter traces Max-Heapify, bottom-up construction, extraction, key updates, heapsort and priority-queue operations while keeping active heap size separate from total array length.
Completeness fills every level from left to right before beginning another.
With zero-based positions, the children of i are two i plus one and two i plus two when those positions are below heap size; the parent of a non-root position is floor of i minus one divided by two. These formulas rely on the absence of holes. They describe shape only and do not imply that the array is globally sorted.
The max-heap order property requires every parent to be at least as large as each child.
It guarantees that the maximum sits at the root, but siblings and cousins need no relative order. Arbitrary-key search can therefore remain linear. A heap is designed for repeated access to one extreme, not for binary-search-style lookup or complete sorted traversal.
Max-Heapify assumes that both child subtrees already satisfy heap order.
Compare the current key with every active child, swap with the larger child if needed, and continue only along the branch that received the smaller key. The other subtree remains valid by the precondition.
A trace should show the active index, child indices, chosen key and resulting array until the moved key dominates its children or reaches a leaf.
Bottom-up construction starts at the final internal node and moves toward the root because leaves are already heaps. Although one call can descend logarithmically, most nodes begin near the leaves and travel little.
Grouping nodes by height gives a weighted sum proportional to n, so building is linear. Repeated insertion is also correct but gives the looser O of n log n construction method.
A priority queue promises removal by priority. A max-heap reads the maximum in constant time and supports insert, extract and suitable key changes in logarithmic time.
Increasing a key may violate the relation with its parent, so it moves upward; decreasing one may violate relations with children, so it moves downward. The data type and representation remain distinct: sorted or unsorted arrays offer different operation trade-offs.
Heapsort first builds a max-heap, then exchanges the root with the last active item, reduces heap size and repairs the root.
The extracted maximum stays in a growing sorted suffix. Child tests must use heap size rather than physical array length so suffix entries never re-enter the heap. Linear construction followed by n logarithmic repairs gives O of n log n time, with constant auxiliary array storage under the usual implementation.
What this chapter covers
- 01
Complete binary-tree shape
- 02
Heap parent-child property
- 03
Array index mapping
- 04
Max-Heapify precondition
- 05
Bottom-up heap construction
- 06
Heapsort and priority queues
Worked example · free
Heapify a violated root
- 2Choose the larger child at the root.
- 3Continue at the moved key.
- 2Verify the final heap property.
Key terms
- Max-Heap
- A complete binary tree in which every parent is at least as large as its children.
- Heap Size
- The number of array positions currently belonging to the active heap.
- Heapify
- A downward repair performed when child subtrees are already heaps.
- Priority Queue
- An abstract type that removes an item according to priority.
Heaps and Priority Queues FAQ
Why is a heap not a sorted array?
The heap property constrains only parent-child relationships. Siblings and different subtrees need not be ordered, so arbitrary-key search may still inspect many items across the structure.
Why does Heapify run in logarithmic time?
Each swap moves the active key down one level along a single path, and a complete binary tree has logarithmic height, so only logarithmically many swaps are possible before reaching a leaf.
Why is bottom-up heap construction linear?
Most nodes are close to leaves and can move only a short distance. Summing actual travel over all nodes is O(n), tighter than multiplying every node by full height.
Exam move
Translate between the array and tree on every practice example. Mark heap size explicitly during extraction and never use the sorted suffix as a child region. Trace one upward key repair and one downward heapify, naming the precondition that makes a single path sufficient. Compare bottom-up construction with repeated insertion on the same keys.
During heapsort, draw the active boundary after each root exchange and audit parent-child order only inside that boundary.
Working through Heaps and Priority Queues in COMP5112? Sia is AskSia’s AI Computer Science tutor — ask any COMP5112 Heaps and Priority Queues question and get a clear, step-by-step explanation grounded in how COMP5112 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
