Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in C++

MeldableHeap: A Randomized Meldable Heap

Explore the MeldableHeap data structure, a flexible randomized heap that merges two heaps efficiently. Understand how its add and remove operations work via randomized merges in expected logarithmic time, and analyze its performance with random walks and entropy concepts.

We'll cover the following...

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:

C++
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 merge(h1, h2) runs in O(log⁡n)O(\log n) expected time, where nn 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:

C++
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⁡(n+1))O(\log(n+1)) = O(log⁡n)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:

C++
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⁡n)O(\log n) expected time.

Additionally, a MeldableHeap can implement many other operations in O(log⁡n)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)O(\log n) ...