TAOCP 5.2.3 Exercise 19

Let the heap be stored in an array `K[1.

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.3: Sorting by Selection

Exercise 19. [21] Design an algorithm that deletes a given element of a heap of length $N$, producing a heap of length $N - 1$.

Verified: no
Solve time: 10m17s

Solution

Let the heap be stored in an array K[1..N] satisfying the heap condition

[ K[\lfloor j/2\rfloor] \ge K[j] \qquad (1 \le \lfloor j/2\rfloor < j \le N). ]

We are given an index i (1 ≤ i ≤ N) of the element to be deleted. The following algorithm removes K[i] and restores the heap property on the remaining N-1 elements, using the same array.

Algorithm D (Delete from a heap)

D1. Replace. Set K[i] ← K[N].

D2. Shrink. Set N ← N - 1.

D3. Heapify if necessary. If i ≤ N (i.e., the deleted element was not the last one), restore the heap property at position i by the following procedure:

  • D3a. Sift up? If i > 1 and K[i] > K[⌊i/2⌋], then repeatedly swap K[i] ↔ K[⌊i/2⌋] and set i ← ⌊i/2⌋ until either i = 1 or K[i] ≤ K[⌊i/2⌋].
  • D3b. Otherwise sift down. While 2i ≤ N, let j ← 2i. If j+1 ≤ N and K[j+1] > K[j], set j ← j+1. If K[i] ≥ K[j], terminate; otherwise swap K[i] ↔ K[j], set i ← j, and repeat.

Correctness

After step D2 the array contains exactly the desired multiset of keys. The heap property can be violated only at nodes on the path from the modified position i to the root (if the new key is larger than its parent) or on a path from i to a leaf (if the new key is smaller than one of its children). All other nodes retain their original parent and children, so the heap condition still holds for them.

If K[i] > K[⌊i/2⌋] we enter the sift‑up loop. Let X be the value that moves upward and P the value it swaps with. Before the swap we have X > P. Because the original structure was a heap, P was ≥ both of its children. Hence after the swap X is ≥ both children at the parent position. The value P moves down to the child position; its new children are exactly the children that P had before (one of them is the former position of X). In the original heap P was the parent of that child position, so P was ≥ the value that originally resided there, and that value was ≥ its own children. Consequently P is ≥ its new children. Thus the heap property holds at both affected nodes. The same reasoning applies inductively at each step of the sift‑up. When the loop stops, X is either at the root or ≤ its parent, and the entire tree satisfies the heap condition.

If K[i] ≤ K[⌊i/2⌋] we enter the sift‑down loop. This is the standard HEAPIFY procedure: at each step we swap the current value with its larger child. The swap makes the parent ≥ both children, and the value that moves down is ≤ its new parent (the larger child). The loop maintains the invariant that the subtree rooted at the current i is a heap except possibly along the path being followed. When the loop terminates, the heap property holds everywhere.

Therefore the algorithm produces a valid heap of size N-1.

Complexity

Both the sift‑up and sift‑down phases follow a single path in the tree, whose length is at most ⌊lg N⌋. Hence the algorithm performs O(log N) comparisons and swaps.

Remarks

  • If the deleted element is the last one (i = N), step D1 is a no‑op, step D2 simply discards it, and step D3 is skipped because i > N. This correctly leaves a heap of size N-1.
  • The same idea works for a min‑heap by reversing the comparisons.

This completes the proof. ∎