Exercises — Heap — max-heap and min-heap properties

Size $n=7$. Internal nodes: indices $i$ with $2i+1<7$, i.e. $i=0,1,2$. Leaves: $3,4,5,6$.

• $i=0$ (val 10): children at 1 (=8), 2 (=9). $10\ge 8$ ✓, $10\ge 9$ ✓.
• $i=1$ (val 8): children at 3 (=4), 4 (=7). $8\ge 4$ ✓, $8\ge 7$ ✓.
• $i=2$ (val 9): children at 5 (=5), 6 (=3). $9\ge 5$ ✓, $9\ge 3$ ✓. Every parent dominates both children → valid max-heap. (Note child 8 at index 1 is smaller than sibling-subtree value 9 — siblings are unordered, that's allowed.)

$n=7$, internal nodes $0,1,2$.

• $i=0$ (1): children 3, 2 → $1\le 3$ ✓, $1\le 2$ ✓.
• $i=1$ (3): children 6, 5 → $3\le 6$ ✓, $3\le 5$ ✓.
• $i=2$ (2): children 9, 8 → $2\le 9$ ✓, $2\le 8$ ✓. Valid min-heap.

$n=5$, internal nodes $0,1$.

• $i=0$ (9): children 12 (idx 1), 8 (idx 2). $9\ge 12$? No → violation (9,12). $9\ge 8$ ✓.
• $i=1$ (12): children 3 (idx 3), 4 (idx 4). $12\ge 3$ ✓, $12\ge 4$ ✓. One violating pair: root 9 vs left child 12.

$n=6$. Push the too-small root toward the leaves.

• $i=0$ (4): children 10 (idx1), 9 (idx2). Larger child = 10. $4<10$ → swap. [10, 4, 9, 2, 8, 7].
• Follow the 4 to $i=1$: children 2 (idx3), 8 (idx4). Larger = 8. $4<8$ → swap. [10, 8, 9, 2, 4, 7].
• Follow to $i=4$: $2\cdot 4+1=9\ge 6$ → leaf, stop. Result [10, 8, 9, 2, 4, 7]. We swapped with the larger child each time so the new parent dominates the other child automatically.

Append at the next free leaf to keep the shape complete: [14, 10, 12, 5, 8, 11, 15], new index 6.

• $\text{parent}(6)=\lfloor 5/2\rfloor =2$ (val 12). Max rule: parent ≥ child? $12\ge 15$? No → swap. [14, 10, 15, 5, 8, 11, 12]. Now the 15 is at index 2.
• $\text{parent}(2)=\lfloor 1/2\rfloor =0$ (val 14). $14\ge 15$? No → swap. [15, 10, 14, 5, 8, 11, 12]. At index 0 → root, stop. Result [15, 10, 14, 5, 8, 11, 12] — 15 bubbled to the top.

Standard extract-max: (1) save root, (2) move last element to root, (3) shrink, (4) sift-down.

• Save 15. Last element = 12 → root. Shrink: [12, 10, 14, 5, 8, 11], $n=6$.
• Sift-down from $i=0$ (12): children 10 (idx1), 14 (idx2). Larger = 14. $12<14$ → swap. [14, 10, 12, 5, 8, 11].
• Follow 12 to $i=2$: children 11 (idx5). $2\cdot 2+1=5<6$. Larger child = 11. $12\ge 11$ ✓ → stop. Returned max = 15, remaining heap [14, 10, 12, 5, 8, 11] (valid).

The minimum must be a leaf. Reason: if the minimum sat at an internal node, it would have a child, and every child is $\le$ its parent in... no — in a max-heap children are $\le$ parent. So an internal node's children are all $\le$ it, meaning some descendant is $\le$ the node — the node can't be the unique smallest unless it has no children. Formally: any internal node has a child $\le$ itself, so a strictly-smaller value exists below it, so an internal node cannot be the minimum. Hence the minimum lives among the leaves. Leaves are the indices with $2i+1\ge n$, i.e. indices $\lfloor n/2\rfloor \dots n-1$. The minimum can be at any leaf index, roughly the last half of the array.

The largest is at the root (index 0). The second largest must be a child of the root — index 1 or index 2. Why? Any element $x$ that is not the root has a parent $\ge x$. If $x$ were second-largest but not a root-child, its parent would be some non-root node, and that parent is $\ge x$ and $\ne$ root, giving a third value between $x$ and the max — contradiction with $x$ being second. So second-largest sits at index 1 or 2. Cost: compare $A[1]$ and $A[2]$, take the larger → $O(1)$.

A node $i$ is internal iff it has a left child, i.e. $2i+1\le n-1\Rightarrow i\le \frac{n-2}{2}\Rightarrow i\le \lfloor \frac{n-2}{2}\rfloor =\lfloor n/2\rfloor -1$. So internal indices are $0\dots \lfloor n/2\rfloor -1$, giving $\lfloor n/2\rfloor$ internal nodes. The rest are leaves: $\text{leaves}=n-\lfloor n/2\rfloor =\lceil n/2\rceil .$ For $n=7$: $\lceil 7/2\rceil =4$ leaves (indices 3,4,5,6) — matches L1.1.

$n=6$. Internal nodes: $i=0,1,2$ (since $2\cdot 2+1=5<6$). Process highest index first: $2,1,0$.

• $i=2$ (val 6): child 4 (idx5). $6\ge 4$ ✓ → no change. [3, 1, 6, 5, 2, 4].
• $i=1$ (val 1): children 5 (idx3), 2 (idx4). Larger = 5. $1<5$ → swap. [3, 5, 6, 1, 2, 4]. Follow 1 to idx3 → leaf ($2\cdot 3+1=7\ge 6$), stop.
• $i=0$ (val 3): children 5 (idx1), 6 (idx2). Larger = 6. $3<6$ → swap. [6, 5, 3, 1, 2, 4]. Follow 3 to idx2: child 4 (idx5). $3\ge 4$? No → swap. [6, 5, 4, 1, 2, 3]. Follow 3 to idx5 → leaf, stop. Result [6, 5, 4, 1, 2, 3] — verify: root 6 ≥ {5,4} ✓; 5 ≥ {1,2} ✓; 4 ≥ {3} ✓. Valid max-heap.

Referenced by Build-Heap (Heapify) O(n): doing it bottom-up costs $O(n)$, not $O(n\log n)$.

Heapsort keeps a "heap region" at the front and a growing sorted tail at the back.

• Step 1: swap root (6) with last (3): [3, 5, 4, 1, 2, | 6]. Heap region size 5. Sift-down idx0 (3): children 5,4 → larger 5, swap. [5, 3, 4, 1, 2, |6]. Follow to idx1 (3): children 1,2 → larger 2, $3\ge 2$ ✓ stop. Sorted tail: [6].
• Step 2: swap root (5) with last-of-region (2, idx4): [2, 3, 4, 1, | 5, 6]. Heap size 4. Sift-down idx0 (2): children 3 (idx1), 4 (idx2) → larger 4, swap. [4, 3, 2, 1, |5, 6]. Follow to idx2 (2): $2\cdot 2+1=5$ ≥ heap size 4 → leaf, stop. Sorted tail: [5, 6]. After two extracts: array [4, 3, 2, 1, 5, 6], the last two positions 5,6 are the final sorted values. Continuing would produce [1,2,3,4,5,6]. See Heapsort.

True — prove it. For a descending array, $A[0]\ge A[1]\ge \cdots \ge A[n-1]$. For any node $i$ its children are at $2i+1$ and $2i+2$, both $>i$. Since the array is non-increasing, $A[i]\ge A[2i+1]$ and $A[i]\ge A[2i+2]$ whenever those indices exist. That is exactly the max-heap order property for every node. Hence any descending-sorted array is a valid max-heap. (The converse is false: [6,5,4,1,2,3] from L4.1 is a valid max-heap but not sorted.) Test case [7,6,5,4,3,2,1]: root 7 ≥ {6,5}; 6 ≥ {4,3}; 5 ≥ {2,1} → valid.

Not possible in general with the simple array heap. To merge, you must produce a single complete tree over all $n+m$ elements obeying heap order. Even just placing every element into the combined array touches $\Theta (n+m)$ slots, and running build-heap on the concatenation costs $O(n+m)$ (from Build-Heap (Heapify) O(n)). Since $O(n+m)>O(\log (n+m))$ for large inputs, $O(\log (n+m))$ merge is impossible for binary array heaps. (Specialised structures — binomial/pairing heaps — achieve $O(\log n)$ merge, but not the plain complete-binary-tree array heap of this note.) Verdict: the claim is false for array heaps.

Every internal node $i$ is compared against each existing child. A node with two children costs 2 comparisons; a node with one child costs 1. In a complete tree exactly one node may have a single child (the parent of the very last leaf, when $n$ is even). Let $L=\lfloor n/2\rfloor$ be the number of internal nodes (from L3.3).

• If $n$ is odd: every internal node has two children → $2L=2\lfloor n/2\rfloor =n-1$ comparisons.
• If $n$ is even: one internal node has a single child → $2L-1=n-1$ comparisons. In both cases the total is exactly $\boxed{n-1}$ comparisons. For $n=7$: $6$ comparisons.

Where can the minimum of a max-heap be? ::: At any leaf (indices $\lfloor n/2\rfloor \dots n-1$). Second-largest in a max-heap lives where? ::: At index 1 or 2 (a child of the root); $O(1)$ to find. Number of leaves of an $n$-node heap? ::: $\lceil n/2\rceil$. Number of internal nodes? ::: $\lfloor n/2\rfloor$. Comparisons to verify max-heap order? ::: exactly $n-1$. Build-heap direction and why? ::: Bottom-up, so sift-down always sits above valid sub-heaps. In sift-down of a max-heap, swap with which child? ::: The larger child. Can two array heaps merge in $O(\log (n+m))$? ::: No — placement/build-heap costs $O(n+m)$.