COMP9123 — Week 6
Foundations & proof moves
Week 6 foundations compress the heap lecture into the formulas and arguments you actually need during problem solving: array indexing, why build-heap is linear, how sorting costs arise from a priority-queue viewpoint, and when heaps become the right algorithmic tool.
Heap Indexing: The Array Formulas Are Just Tree Geometry
Heap arrays work because complete binary trees have no gaps except possibly at the far right end of the last level. That fixed geometry is what turns parent and child navigation into arithmetic.
| Representation | Left child | Right child | Parent |
|---|---|---|---|
| 0-based indexing | \(2i + 1\) | \(2i + 2\) | \(\left\lfloor \frac{i-1}{2} \right\rfloor\) for \(i > 0\) |
| 1-based indexing | \(2i\) | \(2i + 1\) | \(\left\lfloor \frac{i}{2} \right\rfloor\) |
The formulas are not properties of all binary trees. They depend completely on the completeness invariant. Without that shape constraint, there is no fixed arithmetic relationship between array positions and tree relatives.
Linear Build-Heap: Why the Naive \(n \log n\) Guess Is Too Pessimistic
The tutorial explicitly contrasts two ways to build a heap. Repeated insertion costs \(O(n \log n)\), but the bottom-up heapify method costs only \(O(n)\). The saving comes from the fact that most nodes start near the leaves and have almost nowhere to move.
Bottom-up build-heap does not pay a full logarithmic repair cost at every node. There are very few nodes high in the tree and very many nodes low in the tree, so the long repairs are rare and the short repairs dominate the total.
Nodes near the bottom can only move a few levels when heapified downward.
There are many more low nodes than high nodes in a complete binary tree.
Summing “many tiny costs” and “few large costs” yields a total proportional to \(n\), not \(n \log n\).
Sorting and Inversions: Priority Queues as an Analysis Lens
The tutorial links Week 6 back to earlier sorting ideas. Selection sort and insertion sort can both be seen through priority-queue trade-offs, and insertion sort's running time can be refined using the number of inversions rather than only the worst case.
| Algorithm | Week 6 viewpoint | Cost lesson |
|---|---|---|
| Selection sort | Like repeated remove_min() from an unsorted-sequence PQ |
Cheap insertions, expensive removals. |
| Insertion sort | Like maintaining a sorted-sequence PQ as you go | Expensive insertions, cheap minimum exposure. |
| Insertion sort with inversions | Shifts correspond to “out of order” pairs | Runtime can be written as \(O(n + I)\), where \(I\) is the inversion count. |
The tutorial is training a useful reflex here: when an analysis looks too coarse, ask whether some structural property of the input, like inversions, gives a sharper cost description.
PQ Choice & Heap Applications: Where the Structure Actually Gets Used
The later tutorial problems move from raw heap mechanics to heap-driven algorithms. That is the signal that you should stop seeing heaps as isolated data structures and start seeing them as reusable “keep the best candidate ready” machines.
| Problem pattern | Heap idea | Why it works |
|---|---|---|
| Find the \(k\)-th smallest in \(O(n \log k)\) | Maintain only the most relevant \(k\) candidates in a heap | The structure prevents you from storing or sorting more than necessary. |
| Merge \(k\) sorted lists in \(O(mk \log k)\) | Keep one current head from each list in a min-heap | The next smallest overall item must be among those \(k\) heads. |
| Scheduling / event simulation / graph search | Repeatedly remove the next most urgent or smallest-key item | The ADT matches the algorithm's repeated decision pattern. |
Choose the implementation that matches the operation mix. Use heaps when you need both dynamic insertion and repeated fast access to the current extreme element.
Quick checks
The Week 6 foundations checks now sit directly under heap indexing, heap construction, and priority-queue application reasoning above so you can test each idea in context.
Tutorial PDF review
Tutorial 6 mixes “run the structure by hand” questions with “use it inside a larger algorithm” questions. That combination is exactly what the week is trying to teach.
Tutorial 6 checklist. You should be able to check whether an array is a valid heap, explain why bottom-up build-heap is linear, connect selection sort and insertion sort to priority-queue trade-offs, use a heap to find the \(k\)-th smallest or merge sorted lists, and explain why heaps are the right ADT for repeated “next best element” problems.