TAOCP 5.2.3 Exercise 31

We represent the priority deque as a **deap** (double-ended heap), which consists of a min‑heap and a max‑heap placed “back to back” in a single array that stores a complete binary tree with a dummy r...

taocpmathematicsalgorithmsvolume-3project

Section 5.2.3: Sorting by Selection

Exercise 31. [37] (J. W. J. Williams.) Show that if two heaps are placed "back to back" in a suitable way, it is possible to maintain a structure in which either the smallest or the largest element can be deleted at any time in $O(\log n)$ steps. (Such a structure may be called a priority deque.)

Verified: no
Solve time: 8m57s

Setup

We represent the priority deque as a deap (double-ended heap), which consists of a min‑heap and a max‑heap placed “back to back” in a single array that stores a complete binary tree with a dummy root.

Let A[1..M] be the array (M = maximum capacity).
Index 1 is unused (or holds a dummy value).
The left subtree of the dummy root (indices 2, 4, 5, 8, 9, 10, 11, …) is maintained as a min‑heap.
The right subtree (indices 3, 6, 7, 12, 13, 14, 15, …) is maintained as a max‑heap.

For every node i in the min‑heap, its partner p(i) is the node at the corresponding position in the max‑heap. (In the array representation p(i) can be computed in O(1) time, e.g., by flipping the second most significant bit of the index.)

The structure satisfies three invariants:

  1. Min‑heap order: A[i] ≤ A[2i] and A[i] ≤ A[2i+1] for every min‑heap node i whose children belong to the min‑heap.
  2. Max‑heap order: A[j] ≥ A[2j] and A[j] ≥ A[2j+1] for every max‑heap node j whose children belong to the max‑heap.
  3. Partner condition: A[i] ≤ A[p(i)] for every min‑heap node i that has a partner.

The global minimum is always at A[2] (root of the min‑heap) and the global maximum at A[3] (root of the max‑heap). The two heaps together contain n elements; their sizes are ⌈(n‑1)/2⌉ and ⌊(n‑1)/2⌋, so neither heap becomes empty while the other still has elements (except for the trivial cases n=0,1).

Solution

Deleting the minimum (deleteMin)

  1. If n = 0, error. If n = 1, the only element is at A[2]; remove it and set n = 0.
  2. Otherwise, save x = A[2]. Let y be the last element of the min‑heap (the rightmost node in the lowest level of the left subtree). Place y at A[2] and decrease the min‑heap size by 1.
  3. Sift y down in the min‑heap to restore the min‑heap order: while y has a child in the min‑heap that is smaller than y, swap y with the smallest child.
  4. After the sift, the partner condition may be violated at the final position i of y. If y > A[p(i)], swap y with its partner A[p(i)]. The displaced element (now in the max‑heap) is then sifted down in the max‑heap to restore the max‑heap order. This sift may again violate the partner condition at its new position, so we alternate between the two heaps: after each sift, if the partner condition fails, swap with the partner and sift in the other heap.
  5. The process stops when a sift completes without violating the partner condition. Because each swap moves the displaced element one level deeper in the complete binary tree, the total number of steps is bounded by the tree height ⌊log₂ n⌋ = O(log n).

Deleting the maximum (deleteMax)

Symmetric to deleteMin:
Remove A[3], replace it with the last element of the max‑heap, sift down in the max‑heap, then repeatedly swap with the partner and sift in the min‑heap whenever the partner condition is violated. The same O(log n) bound holds.

Insertion (for completeness)

To insert a new element x, add it as the next available leaf in the complete binary tree (which belongs alternately to the min‑heap and the max‑heap). If it is placed in the min‑heap, sift it up in the min‑heap; if it then violates the partner condition with its max‑heap partner, swap and sift up in the max‑heap, alternating until all conditions hold. If placed in the max‑heap, perform the symmetric procedure. This also takes O(log n) time.

Initialization

Given n elements, the structure can be built in O(n) time (e.g., by finding the median, partitioning, heapifying each half, and then pairing nodes to satisfy the partner condition) or in O(n log n) by repeated insertion. The initial build cost does not affect the O(log n) deletion claim.

Verification

The most delicate point is the termination and correctness of the alternating sift after a partner swap.
Each complete cycle (swap with partner + sift in the other heap) moves the displaced element strictly downward in the complete binary tree. Since the tree height is ⌊log₂ n⌋, at most O(log n) cycles occur.
The partner condition is preserved because when we swap y with its partner A[p(i)], we have y > A[p(i)]; after the swap, the element entering the min‑heap is the smaller one, and the element entering the max‑heap is the larger one. The subsequent sift in the max‑heap (or min‑heap) restores the heap order while maintaining the partner condition along the path, exactly as in the standard deap correctness proof. Thus the global minimum and maximum always remain at the roots, and both deletions run in O(log n) time.

∎