Data Structures with Generic Types in Python/

...

/

MeldableHeap: A Randomized Meldable Heap

MeldableHeap: A Randomized Meldable Heap

Learn the meldable heap and its operations.

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 below illustration:

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:

Press + to interact
class MeldableHeap(BinaryTree, BaseSet):

    class Node(BinaryTree.Node):

        def __init__(self, x):

            super(MeldableHeap.Node, self).__init__()

            self.x = x

            

    def __init__(self, iterable=[]):

        super(MeldableHeap, self).__init__()

        self.n = 0

        

    def merge(self, h1, h2):

        if h1 == self.nil: return h2

        if h2 == self.nil: return h1

        if h2.x < h1.x: (h1, h2) = (h2, h1)

        if random_bit():

            h1.left = self.merge(h1.left, h2)

            h1.left.parent = h1

        else:

            h1.right = self.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:

Press + to interact
class MeldableHeap(BinaryTree, BaseSet):

    class Node(BinaryTree.Node):

        def __init__(self, x):

            super(MeldableHeap.Node, self).__init__()

            self.x = x

            

    def __init__(self, iterable=[]):

        super(MeldableHeap, self).__init__()

        self.n = 0



    def add(self, x):

        u = self._new_node(x)

        self.r = self.merge(u, self.r)

        self.r.parent = self.nil

        self.n += 1

        return True

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

The 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:

Press + to interact
class MeldableHeap(BinaryTree, BaseSet):

    class Node(BinaryTree.Node):

        def __init__(self, x):

            super(MeldableHeap.Node, self).__init__()

            self.x = x

            

    def __init__(self, iterable=[]):

        super(MeldableHeap, self).__init__()

        self.n = 0

    

    def remove(self):

        if self.n == 0: raise IndexError('remove from empty heap')

        x = self.r.x

        self.r = self.merge(self.r.left, self.r.right)

        if self.r != self.nil: self.r.parent = self.nil

        self.n -= 1

        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) 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 nodes is at most log⁡(n+1).\log(n + 1).

Proof: The proof is by induction on n. In the base case, n=0n = 0 and the walk has length 0=log⁡(n+1)\text{length } 0 = \log(n+1). Suppose now that the result is true for all non-negative integers n′<nn^{\prime} < n.

Let n1n_{1} ...