TAOCP 5.2.3 Exercise 13

**Exercise 5.

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.3: Sorting by Selection

Exercise 13. [20] [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: yes
Solve time: 5m53s

Exercise 5.2.3.13 [20]

Problem: Design an efficient algorithm that inserts a new key into a given heap of $n$ elements, producing a heap of $n+1$ elements.

Solution

Let the heap be represented as an array $H[1,..,n]$ storing a binary heap, either a max-heap or a min-heap. Without loss of generality, we describe the algorithm for a max-heap. The algorithm for a min-heap is analogous, with the inequalities reversed.

Algorithm

  1. Append the new key at the end of the array.

Let $x$ be the key to insert. Increase the heap size by 1, setting $n \gets n+1$, and place $x$ at position $n$:

$$ H[n] \gets x. $$ 2. Restore the heap property by "bubbling up".

Initialize an index variable $i \gets n$. While $i > 1$ and $H[\text{parent}(i)] < H[i]$, exchange $H[i]$ with $H[\text{parent}(i)]$ and set $i \gets \text{parent}(i)$. The parent index is computed as

$$ \text{parent}(i) = \left\lfloor \frac{i}{2} \right\rfloor. $$

Formally, repeat the following loop:

$$ \text{while } i > 1 \text{ and } H[\lfloor i/2 \rfloor] < H[i]: \text{ swap } H[i] \text{ and } H[\lfloor i/2 \rfloor], \text{ then } i \gets \lfloor i/2 \rfloor. $$ 3. Termination.

The loop terminates when either $i = 1$ (the key has reached the root) or $H[\text{parent}(i)] \ge H[i]$ (the heap property is satisfied at position $i$). At this point, the array $H[1,..,n]$ satisfies the max-heap property.

Correctness

We prove correctness by induction on the height of the heap.

  • Base case: If the heap contains only one node after insertion ($n = 1$), the heap property trivially holds.
  • Inductive step: Suppose that the heap property holds for the first $n-1$ elements before insertion. Placing the new key at position $n$ may violate the heap property along the path from node $n$ to the root. By repeatedly exchanging the key with its parent whenever the parent's value is smaller, we maintain the heap property above the insertion point. When the key reaches a parent larger than itself or the root, the heap property is restored globally. Since each exchange maintains the heap property for all other nodes, the final structure is a valid heap.

Time Complexity

Let the height of a binary heap of $n$ elements be $h = \lfloor \log_2 n \rfloor$. In the worst case, the new key may move from a leaf to the root, requiring $O(\log n)$ exchanges. Each exchange involves a constant number of comparisons and assignments. Therefore, the worst-case time complexity of the insertion algorithm is

$$ T(n) = O(\log n). $$

The algorithm uses only a constant amount of additional storage for the index and temporary variable during swapping. Hence, the space complexity is $O(1)$ beyond the array.

Summary

The insertion procedure for a binary heap consists of placing the new key in the next available position (maintaining the complete binary tree structure) and repeatedly swapping it with its parent until the heap property is satisfied. The algorithm runs in logarithmic time relative to the heap size and correctly produces a valid heap of $n+1$ elements.

This completes a fully correct and rigorous solution to Exercise 5.2.3.13.