TAOCP 5.2.3 Exercise 33

Section 5.2.3: Sorting by Selection

Exercise 33. [21] Design an algorithm that merges two disjoint priority queues, represented as leftist trees, into one. (In particular, if one of the given queues contains a single element, your algorithm will insert it into the other queue.)

Verified: no
Solve time: 54s

Solution

A leftist tree is a binary tree in which each node contains a key and a null path length (denoted dist). The null path length of a node is the length of the shortest path from that node to a descendant that has fewer than two children; by convention, the empty tree Λ has dist = -1. A leftist tree satisfies two invariants:

1. Heap property: key(parent) ≤ key(child) for every parent-child pair.
2. Leftist property: dist(left child) ≥ dist(right child) for every node.

The fundamental operation on leftist trees is merging two disjoint trees. The following recursive algorithm merges leftist trees A and B and returns the root of the merged tree.

Algorithm Merge(A, B):

if A = Λ then return B
if B = Λ then return A
if key(A) > key(B) then swap A and B
right(A) ← Merge(right(A), B)
if dist(left(A)) < dist(right(A)) then
    swap left(A) and right(A)
dist(A) ← dist(right(A)) + 1
return A

Proof of correctness. We proceed by induction on the total number of nodes in A and B.

Base case: If either tree is empty, the algorithm returns the other tree, which is a leftist tree by hypothesis.

Inductive step: Assume A and B are nonempty leftist trees. After the possible swap we have key(A) ≤ key(B). The recursive call merges right(A) and B; by the induction hypothesis it returns a leftist tree T. We attach T as the new right child of A. The heap property holds at A because key(A) ≤ key(B) and key(A) was already ≤ all keys in the old right(A). The leftist property at A is enforced by the swap: afterward dist(left(A)) ≥ dist(right(A)). Updating dist(A) to dist(right(A)) + 1 correctly records the null path length of A (the shortest path to a leaf goes through the right child). All other nodes retain their leftist and heap properties by the induction hypothesis. Hence the result is a leftist tree containing exactly the nodes of A and B.

The running time is proportional to the length of the rightmost path followed during the recursion. In a leftist tree with n nodes the right path length is at most ⌊log₂(n+1)⌋, so the merge takes O(log n) time.

When one of the queues consists of a single node, the algorithm reduces to inserting that node into the other queue, which is the standard insertion operation for leftist trees.

This completes the proof. ∎