10.2 MeldableHeap: A Randomized Meldable Heap

In this section, we describe the MeldableHeap, a priority Queue implementation in which the underlying structure is also a heap-ordered binary tree. However, unlike a BinaryHeap in which the underlying binary tree is completely defined by the number of elements, there are no restrictions on the shape of the binary tree that underlies a MeldableHeap; anything goes.

The $\mathtt{add(x)}$ and $\mathtt{remove()}$ operations in a MeldableHeap are implemented in terms of the $\mathtt{merge(h1,h2)}$ operation. This operation takes two heap nodes $\mathtt{h1}$ and $\mathtt{h2}$ and merges them, returning a heap node that is the root of a heap that contains all elements in the subtree rooted at $\mathtt{h1}$ and all elements in the subtree rooted at $\mathtt{h2}$.

The nice thing about a $\mathtt{merge(h1,h2)}$ operation is that it can be defined recursively. If either of $\mathtt{h1}$ or $\mathtt{h2}$ is $\mathtt{nil}$, then we are merging with an empty set, so we return $\mathtt{h2}$ or $\mathtt{h1}$, respectively. Otherwise, assume $\ensuremath{\mathtt{h1.x}} \le \ensuremath{\mathtt{h2.x}}$ since, if $\ensuremath{\mathtt{h1.x}} > \ensuremath{\mathtt{h2.x}}$, then we can reverse the roles of $\mathtt{h1}$ and $\mathtt{h2}$. Then we know that the root of the merged heap will contain $\mathtt{h1.x}$ and we can recursively merge $\mathtt{h2}$ with $\mathtt{h1.left}$ or $\mathtt{h1.right}$, as we wish. This is where randomization comes in, and we toss a coin to decide whether to merge $\mathtt{h2}$ with $\mathtt{h1.left}$ or $\mathtt{h1.right}$:

    Node<T> merge(Node<T> h1, Node<T> h2) {
        if (h1 == nil) return h2;
        if (h2 == nil) return h1;
        if (compare(h2.x, h1.x) < 0) return merge(h2, h1);
        // now we know h1.x <= h2.x
        if (rand.nextBoolean()) {
            h1.left = merge(h1.left, h2);
            h1.left.parent = h1;
        } else {
            h1.right = merge(h1.right, h2);
            h1.right.parent = h1;
        }
        return h1;
    }

In the next section, we show that $\mathtt{merge(h1,h2)}$ runs in $O(\log \ensuremath{\mathtt{n}})$ expected time, where $\mathtt{n}$ is the total number of elements in $\mathtt{h1}$ and $\mathtt{h2}$.

With access to a $\mathtt{merge(h1,h2)}$ operation, the $\mathtt{add(x)}$ operation is easy. We create a new node $\mathtt{u}$ containing $\mathtt{x}$ and then merge $\mathtt{u}$ with the root of our heap:

    boolean add(T x) {
        Node<T> u = newNode();
        u.x = x;
        r = merge(u, r);
        r.parent = nil;
        n++;
        return true;
    }

This takes $O(\log (\ensuremath{\mathtt{n}}+1)) = O(\log \ensuremath{\mathtt{n}})$ expected time.

The $\mathtt{remove()}$ operation is similarly easy. The node we want to remove is the root, so we just merge its two children and make the result the root:

    T remove() {
        T x = r.x;
        r = merge(r.left, r.right);
        if (r != nil) r.parent = nil;
        n--;
        return x;
    }

Again, this takes $O(\log \ensuremath{\mathtt{n}})$ expected time.

Additionally, a MeldableHeap can implement many other operations in $O(\log \ensuremath{\mathtt{n}})$ expected time, including:

• $\mathtt{remove(u)}$: remove the node $\mathtt{u}$ (and its key $\mathtt{u.x}$) from the heap.
• $\mathtt{absorb(h)}$: add all the elements of the MeldableHeap $\mathtt{h}$ to this heap, emptying $\mathtt{h}$ in the process.

Each of these operations can be implemented using a constant number of $\mathtt{merge(h1,h2)}$ operations that each take $O(\log \ensuremath{\mathtt{n}})$ time.

10.2.1 Analysis of $\mathtt{merge(h1,h2)}$

The analysis of $\mathtt{merge(h1,h2)}$ is based on the analysis of a random walk in a binary tree. A random walk in a binary tree is a walk that starts at the root of the tree. At each step in the walk, a coin is tossed and the walk proceeds to the left or right child of the current node depending on the result of this coin toss. The walk ends when it falls off the tree (the current node becomes $\mathtt{nil}$).

The following lemma is somewhat remarkable because it does not depend at all on the shape of the binary tree:

Lemma 10..1   The expected length of a random walk in a binary tree with $\mathtt{n}$ nodes is at most $\mathtt{\log (n+1)}$.

Proof. The proof is by induction on $\mathtt{n}$. In the base case, $\ensuremath{\mathtt{n}}=0$ and the walk has length $0=\log (\ensuremath{\mathtt{n}}+1)$. Suppose now that the result is true for all non-negative integers $\ensuremath{\mathtt{n}}'< \ensuremath{\mathtt{n}}$.

Let $\ensuremath{\mathtt{n}}_1$ denote the size of the root's left subtree, so that $\ensuremath{\mathtt{n}}_2=\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{n}}_1-1$ is the size of the root's right subtree. Starting at the root, the walk takes one step and then continues in a subtree of size $\ensuremath{\mathtt{n}}_1$ or continues in a subtree of size $\ensuremath{\mathtt{n}}_2$. By our inductive hypothesis, the expected length of the walk is then

$$\mathrm{E}[W] = 1 + \frac{1}{2}\log (\ensuremath{\mathtt{n}}_1+1) + \frac{1}{2}\log (\ensuremath{\mathtt{n}}_2+1) \enspace ,$$

since each of $\ensuremath{\mathtt{n}}_1$ and $\ensuremath{\mathtt{n}}_2$ are less than $\ensuremath{\mathtt{n}}$. Since $\log$ is a concave function, $\mathrm{E}[W]$ is maximized when $\ensuremath{\mathtt{n}}_1=\ensuremath{\mathtt{n}}_2=(\ensuremath{\mathtt{n}}-1)/2$. Therefore, the expected number of steps taken by the random walk is

$$\mathrm{E}[W] = 1 + \frac{1}{2}\log (\ensuremath{\mathtt{n}}_1+1) + \frac{1}{2}\log (\ensuremath{\mathtt{n}}_2+1)$$

$$\le 1 + \log ((\ensuremath{\mathtt{n}}-1)/2+1)$$

$$= 1 + \log ((\ensuremath{\mathtt{n}}+1)/2)$$

$$= \log (\ensuremath{\mathtt{n}}+1) \enspace . \qedhere$$

$\qedsymbol$

We make a quick digression to note that, for readers who know a little about information theory, the proof of Lemma 10.1 can be stated in terms of entropy.

Proof. [Information Theoretic Proof of Lemma 10.1] Let $d_i$ denote the depth of the $i$th external node and recall that a binary tree with $\mathtt{n}$ nodes has $\mathtt{n+1}$ external nodes. The probability of the random walk reaching the $i$th external node is exactly $p_i=1/2^{d_i}$, so the expected length of the random walk is given by

$$H=\sum_{i=0}^{\ensuremath{\mathtt{n}}} p_id_i =\sum_{i=0}^{\ensu... ...og\left(2^{d_i}\right) = \sum_{i=0}^{\ensuremath{\mathtt{n}}}p_i\log({1/p_i})$$

The right hand side of this equation is easily recognizable as the entropy of a probability distribution over $\ensuremath{\mathtt{n}}+1$ elements. A basic fact about the entropy of a distribution over $\ensuremath{\mathtt{n}}+1$ elements is that it does not exceed $\log (\ensuremath{\mathtt{n}}+1)$, which proves the lemma. $\qedsymbol$

With this result on random walks, we can now easily prove that the running time of the $\mathtt{merge(h1,h2)}$ operation is $O(\log \ensuremath{\mathtt{n}})$.

Lemma 10..2   If $\mathtt{h1}$ and $\mathtt{h2}$ are the roots of two heaps containing $\ensuremath{\mathtt{n}}_1$ and $\ensuremath{\mathtt{n}}_2$ nodes, respectively, then the expected running time of $\mathtt{merge(h1,h2)}$ is at most $O(\log \ensuremath{\mathtt{n}})$, where $\ensuremath{\mathtt{n}}=\ensuremath{\mathtt{n}}_1+\ensuremath{\mathtt{n}}_2$.

Proof. Each step of the merge algorithm takes one step of a random walk, either in the heap rooted at $\mathtt{h1}$ or the heap rooted at $\mathtt{h2}$ The algorithm terminates when either of these two random walks fall out of its corresponding tree (when $\ensuremath{\mathtt{h1}}=\ensuremath{\mathtt{null}}$ or $\ensuremath{\mathtt{h2}}=\ensuremath{\mathtt{null}}$). Therefore, the expected number of steps performed by the merge algorithm is at most

$$\log (\ensuremath{\mathtt{n}}_1+1) + \log (\ensuremath{\mathtt{n}}_2+1) \le 2\log \ensuremath{\mathtt{n}} \enspace . \qedhere$$

$\qedsymbol$

10.2.2 Summary

The following theorem summarizes the performance of a MeldableHeap:

Theorem 10..2   A MeldableHeap implements the (priority) Queue interface. A MeldableHeap supports the operations $\mathtt{add(x)}$ and $\mathtt{remove()}$ in $O(\log \ensuremath{\mathtt{n}})$ expected time per operation.