Randomized meldable heap

In computer science, a randomized meldable heap (also Meldable Heap or Randomized Meldable Priority Queue) is a priority queue based data structure in which the underlying structure is also a heap-ordered binary tree. However, there are no restrictions on the shape of the underlying binary tree.

This approach has a number of advantages over similar data structures. It offers greater simplicity: all operations for the randomized meldable heap are easy to implement and the constant factors in their complexity bounds are small. There is also no need to preserve balance conditions and no satellite information within the nodes is necessary. Lastly, this structure has good worst-case time efficiency. The execution time of each individual operation is at most logarithmic with high probability.^[1]

Operations

The randomized meldable heap supports a number of common operations. These are insertion, deletion, and a searching operation, findMin. The insertion and deletion operations are implemented in terms of an additional operation specific to the meldable heap, Meld(Q1, Q2).

Meld

The basic goal of the meld (also called merge) operation is to take two heaps (by taking each heaps root nodes), Q1 and Q2, and merges them, returning a single heap node as a result. This heap node is the root node of a heap containing all elements from the two subtrees rooted at Q1 and Q2.

A nice feature of this meld operation is that it can be defined recursively. If either heaps are null, then the merge is taking place with an empty set and the method simply returns the root node of the non-empty heap. If both Q1 and Q2 are not nil, check if Q1 > Q2. If it is, swap the two. It is therefore ensured that Q1 < Q2 and that the root node of the merged heap will contain Q1. We then recursively merge Q2 with Q1.left or Q1.right. This step is where the randomization comes in as this decision of which side to merge with is determined by a coin toss.

function Meld(Node Q1, Node Q2)
    if Q1 is nil => return Q2
    if Q2 is nil => return Q1
    if Q1 > Q2 => swap Q1 and Q2
    if coin_toss is 0 => Q1.left = Meld(Q1.left, Q2)
    else Q1.right = Meld(Q1.right, Q2)
    return Q1

Insert

With the meld operation complete, inserting into the meldable heap is easy. First, a new node, u, is created containing the value x. This new node is then simply melded with the heaps root node.

function Insert(x)
    Node u = new Node
    u.x = x
    root = Meld(u, root)
    root.parent = nil
    increment node count

Remove

Similarly easy to the insert operation, Remove() uses the Meld operation to eliminate the root node from the heap. This is done by simply melding the two children of the root node and making the returned node the new root.

function Remove()
    root = Meld(root.left, root.right)
    if root is not nil => root.parent = nil
    decrement node count

FindMin

Possibly the easiest operation for the randomized meldable heap, FindMin() simply returns the element currently stored in the heap's root node.

Additional operations

Some additional operations that can be implemented for the meldable heap that also have O(logn) worst-case efficiency are:

Remove(u) - Remove the node u and its key from the heap.
Absorb(Q) - Add all elements of the meldable heap Q to this heap, emptying Q in the process.
DecreaseKey(u, y) - Decreases the key in node u to y (pre-condition: y <= u.x).

Efficiency analysis

As all non-constant-time operations are defined in terms of the Meld operation, the efficiency of these operations can be determined through analysis of the complexity of melding two randomized heaps.

The result of this analysis is that the expected time of any meldable priority queue operation on a n-node randomized heap is O(logn).^[1]^[2]

Operation	Worst-Case Time Efficiency
Meld(Q1, Q2)	O(logn)
Insert(x)	O(logn)
Remove()	O(logn)
FindMin()	O(1)
Remove(x)	O(logn)
Absorb(Q)	O(logn)

History

The meldable heap appears to have first been proposed in 1998 by Gambin and Malinowski.^[1]

Variants

While the randomized meldable heap is the simplest form of a meldable heap implementation, others do exist. These are:

References

^ ^a ^b ^c A. Gambin and A. Malinowski. 1998. Randomized Meldable Priority Queues. In Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics: Theory and Practice of Informatics (SOFSEM '98), Branislav Rovan (Ed.). Springer-Verlag, London, UK, UK, 344-349.
^ P. Morin, [1] Open Data Structures, p. 191-

[Gambin-1] A. Gambin and A. Malinowski. 1998. Randomized Meldable Priority Queues. In Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics: Theory and Practice of Informatics (SOFSEM '98), Branislav Rovan (Ed.). Springer-Verlag, London, UK, UK, 344-349.

[Morin-2] P. Morin, [1] Open Data Structures, p. 191-

[1]

[2]