Heap: 19-Soft-A1 Algorithms & Data Structures, May 2013, Q3

Question 3: Heap (10 marks: 2; 2,2,2,2)

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.

1. Definition of a max heap

A max heap is a complete binary tree (every level fully filled except possibly the last, which fills left-to-right) that satisfies the max-heap property: every node's key is greater than or equal to the keys of its children. Consequently the maximum element is always at the root, and the array representation from Q2 applies directly (level-order, 0-indexed).

2.I Insertion (2–3 sentences)

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

2.II Deletion (delete-max, 2–3 sentences)

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" or "bubble-down" — until both children are smaller or it has no children.

2.III Pictures: inserting 4, 6, 3, 7, 1 into an empty max heap

Figure 1 — Array-backed max heap after each insertion. Insert 6: 6 > parent 4, so it bubbles up to the root, giving [6,4]. Insert 3: parent (root 6) is already larger, no swap, giving [6,4,3]. Insert 7: 7 > parent 4, swap to [6,7,3,4]; then 7 > parent 6, swap again to [7,6,3,4]. Insert 1: parent is 6, 1 < 6, no swap — final heap [7,6,3,4,1].

2.IV Complexity

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, never a full pass over the array.

Operation	Complexity	Why
Insert (sift-up)	$\boxed{O(\log n)}$	at most one swap per level, height $=\lfloor \log_2 n\rfloor$
Delete-max (sift-down)	$\boxed{O(\log n)}$	same bound, path from root to a leaf
Heap array after inserting 4,6,3,7,1	[7, 6, 3, 4, 1]	traced step by step above

Concept & Theory

Topic. 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$; a full "build-heap" from $n$ unordered elements (repeated sift-down from the last internal node) costs $O(n)$ overall, not $O(n\log n)$, because most nodes are near the bottom and sift only a short distance.

Why this works. Restoring the heap property after a single insertion or removal only ever requires fixing one 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 "building a heap from scratch by $n$ individual inserts" ($O(n\log n)$) with the classical linear-time BUILD-MAX-HEAP ($O(n)$, sifting down from the middle of the array outward) — the two produce a valid heap but at different total cost, and this question only asked about a single insert/delete, not a full build.

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

Question 3 of 8: Heap