Max Heap: 19-Soft-A1 Algorithms & Data Structures, December 2016, Q2

Question 2: Max Heap (20 marks: 5 items, 4 marks each)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A 0-indexed array storing a complete binary tree, level by level. Find. the parent/right-child index formulas, the insert and delete-max procedures, the heap states after inserting 4, 6, 3, 7, 1 into an empty heap, and the time complexity of each operation.

1. Index formulas — 4 marks

a. Parent of index $n$: $\left\lfloor \dfrac{n-1}{2} \right\rfloor$ (integer division truncates); node 0 (the root) has no parent. b. Right child of index $n$: $2n+2$, valid only while that index is still within the array's current size.

2. Insertion — 4 marks

The new value is appended in the next open slot at the end of the array, which keeps the tree complete. It is then compared against its parent and swapped upward ("sift-up") for as long as it is larger than its parent, stopping as soon as the parent is at least as large or the new node reaches the root.

3. Deletion (delete-max) — 4 marks

The root (the maximum) is removed and returned; the last element in the array is moved into the now-empty root slot to keep the tree complete, and the array shrinks by one. That relocated element is then compared against its larger child and swapped downward ("sift-down") until both children are smaller or it has no children.

4. Building the heap: insert 4, 6, 3, 7, 1 — 4 marks

Approach. Insert one value at a time into the array's next free slot, then sift it up while it exceeds its parent.

Insert 4. Empty heap → $[4]$, no parent to compare against.
Insert 6. Appended at index 1, parent is index 0 (value 4); $6>4$ so it swaps up: $[6,4]$.
Insert 3. Appended at index 2, parent is index 0 (value 6); $3<6$, no swap: $[6,4,3]$.
Insert 7. Appended at index 3, parent is index 1 (value 4); $7>4$, swap to $[6,7,3,4]$; new position is index 1, parent index 0 (value 6); $7>6$, swap again to $[7,6,3,4]$.
Insert 1. Appended at index 4, parent is index 1 (value 6); $1<6$, no swap. $$\boxed{[7,6,3,4,1]}$$

Figure 2 — Array-backed max heap after each insertion, with the array strip shown beneath each tree. Final heap: $[7,6,3,4,1]$.

5. Complexity — 4 marks

Both insertion and delete-max run in $O(\log n)$ time. In each case the element being repositioned travels along a single root-to-leaf path, and because the tree is complete its height is $\lfloor \log_2 n \rfloor$, so the sift-up or sift-down loop performs at most $O(\log n)$ comparisons and swaps.

Item	Result
Parent of index $n$	$\lfloor(n-1)/2\rfloor$
Right child of index $n$	$2n+2$
Heap array after inserting 4,6,3,7,1	$\boxed{[7,6,3,4,1]}$
Insert / delete-max complexity	$\boxed{O(\log n)}$ each

Concept & Theory

Topic. Array-backed binary max-heaps and the sift-up / sift-down maintenance operations.

Key relations. Heap property $\text{data}[\text{parent}(i)] \ge \text{data}[i]$ for every $i>0$; tree height for $n$ nodes is $\lfloor\log_2 n\rfloor$; building a heap from $n$ unordered elements by sifting down from the last internal node outward costs $O(n)$ overall (not $O(n\log n)$), because most nodes sit near the bottom and sift only a short distance.

Why this works. Restoring the heap property after one insertion or removal only ever requires fixing a single root-to-leaf path — every other node's relative order is untouched — so the cost is bounded by the tree's height rather than its size.

Common pitfall. Confusing "$n$ individual inserts" ($O(n\log n)$ total) with the classical linear-time build-heap ($O(n)$); and, on the trace itself, stopping the sift-up one comparison too early — insert 7 requires two swaps (past 4, then past 6), not one.

Source. Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms §6.1–6.5 (heaps, build-heap analysis).

Question 2 of 7: Max Heap