Subsections

# 10.2MeldableHeap: 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 and operations in a MeldableHeap are implemented in terms of the operation. This operation takes two heap nodes and and merges them, returning a heap node that is the root of a heap that contains all elements in the subtree rooted at and all elements in the subtree rooted at .

The nice thing about a operation is that it can be defined recursively. See Figure 10.4. If either or is , then we are merging with an empty set, so we return or , respectively. Otherwise, assume since, if , then we can reverse the roles of and . Then we know that the root of the merged heap will contain , and we can recursively merge with or , as we wish. This is where randomization comes in, and we toss a coin to decide whether to merge with or :

    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 runs in expected time, where is the total number of elements in and .

With access to a operation, the operation is easy. We create a new node containing and then merge 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 expected time.

The 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 expected time.

Additionally, a MeldableHeap can implement many other operations in expected time, including:

• : remove the node (and its key ) from the heap.
• : add all the elements of the MeldableHeap to this heap, emptying in the process.
Each of these operations can be implemented using a constant number of operations that each take expected time.

## 10.2.1 Analysis of

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

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 nodes is at most .

Proof. The proof is by induction on . In the base case, and the walk has length . Suppose now that the result is true for all non-negative integers .

Let denote the size of the root's left subtree, so that 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 or . By our inductive hypothesis, the expected length of the walk is then

since each of and are less than . Since is a concave function, is maximized when . Therefore, the expected number of steps taken by the random walk is

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 denote the depth of the th external node and recall that a binary tree with nodes has external nodes. The probability of the random walk reaching the th external node is exactly , so the expected length of the random walk is given by

The right hand side of this equation is easily recognizable as the entropy of a probability distribution over elements. A basic fact about the entropy of a distribution over elements is that it does not exceed , which proves the lemma.

With this result on random walks, we can now easily prove that the running time of the operation is .

Lemma 10..2   If and are the roots of two heaps containing and nodes, respectively, then the expected running time of is at most , where .

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

## 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 and in expected time per operation.

opendatastructures.org