MeldableHeap: A Randomized Meldable Heap

Here, 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.

Operation in MeldableHeap

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

The nice thing about a merge(h1, h2) operation is that it can be defined recursively. See the figure below:

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

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

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

This takes $O(\log(n+1))$ = $O(\log n)$expected time.

The remove() operation is also easy to implement. The node we want to remove is the root, so we just merge its two children and make the result the root:

Again, this takes $O(\log n)$ expected time.

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

• remove(u): Remove the node u (and its key u.x) from the heap.
• absorb(h): Add all the elements of the MeldableHeap h to this heap, emptying h in the process.

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

Analysis of merge(h1, h2)

The analysis of merge(h1, h2) 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 nil).

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

Lemma 1: The expected length of a random walk in a binary tree with n ...