TAOCP 5.2.3 Exercise 16

**Algorithm I** (*Heap insertion*).

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.3: Sorting by Selection

Exercise 16. [20] Design an efficient algorithm that inserts a new key into a given heap of $n$ elements, producing a heap of $n + 1$ elements.

Verified: no
Solve time: 5m10s

Solution

Algorithm I (Heap insertion).
Given a heap (K_1, K_2, \ldots, K_n) satisfying
(K_{\lfloor j/2\rfloor} \ge K_j) for (1 \le \lfloor j/2\rfloor < j \le n),
and a new key (K), this algorithm inserts (K) into the heap, producing a heap of size (n+1).

  1. I1. [Increase size.] Set (n \leftarrow n+1), (K_n \leftarrow K).
  2. I2. [Initialize.] Set (j \leftarrow n).
  3. I3. [Done?] If (j = 1), terminate. Set (i \leftarrow \lfloor j/2\rfloor). If (K_i \ge K_j), terminate.
  4. I4. [Swap.] Exchange (K_i \leftrightarrow K_j).
  5. I5. [Move up.] Set (j \leftarrow i) and go to I3.

Correctness proof.
We prove that upon termination the array (K_1,\ldots,K_n) satisfies the heap condition
(K_{\lfloor j/2\rfloor} \ge K_j) for all (1 \le \lfloor j/2\rfloor < j \le n).

Define the path from the root to a node (v) as the sequence of indices obtained by repeatedly taking (\lfloor \cdot/2\rfloor).
We maintain the following loop invariant at the start of step I3:

Invariant. The heap property holds everywhere except possibly between (K_j) and its parent (K_{\lfloor j/2\rfloor}) (if (j>1)). Moreover, the subtree rooted at (j) (i.e., all descendants of (j)) satisfies the heap property.

Initialization. After I1 and I2 the original heap of size (n-1) was valid. The new key is placed at the last position (n), which is a leaf. The only possible violation is between (K_n) and its parent. The subtree rooted at (n) is a single node, so the invariant holds.

Maintenance. Assume the invariant holds at I3 with (j>1) and let (i = \lfloor j/2\rfloor).
If (K_i \ge K_j) the algorithm terminates and the heap property holds globally.
Otherwise (K_i < K_j) and we swap them. After the swap, the larger element (old (K_j)) moves to (i) and the smaller (old (K_i)) moves to (j). We must show the invariant holds for the new (j = i).

  • The new element at (i) (old (K_j)) is compared with its children (j) (holds old (K_i)) and, if (j) is even, (j+1). Because old (K_j >) old (K_i), it is (\ge) child (j). Before the swap the heap property held between (i) and (j+1) (the only possible violation was between (i) and (j)), so old (K_i \ge K_{j+1}). Since old (K_j >) old (K_i), we have old (K_j \ge K_{j+1}). Thus the new element at (i) is (\ge) both children.
  • The new element at (j) (old (K_i)) becomes the parent of the original children of (j). In the original heap (before any swaps), old (K_i) was an ancestor of the leaf (n) and therefore (\ge) every node in the original subtree rooted at (j). The swaps performed so far have only moved the new key up this path and shifted each ancestor down one level; no other elements have entered the subtree rooted at (j). Hence old (K_i) is still (\ge) the current children of (j). (One can also argue inductively: if (j) was a leaf, it has no children; otherwise, the children of (j) are the node from which the new key came - which now holds the previous ancestor, known to be (\le) old (K_i) - and the sibling of that node, which is an original node (\le) old (K_i) because old (K_i) was its grandparent in the original heap.)

Therefore the invariant is preserved with (j \leftarrow i).

Termination. Since (j \leftarrow \lfloor j/2\rfloor) strictly decreases (j) while (j>1), the loop executes at most (\lfloor \log_2 n\rfloor) times. When it stops, either (j=1) (the new key reached the root) or (K_{\lfloor j/2\rfloor} \ge K_j). In both cases the invariant guarantees the heap property everywhere.

Complexity.
The algorithm makes at most (\lfloor \log_2 n\rfloor) comparisons and exchanges. Hence its running time is (O(\log n)).

∎