Randomized meldable heap

A randomized meldable heap is a type of binary heap data structure that supports the standard priority‑queue operations—insert, find‑minimum, delete‑minimum, and meld (merge)—by maintaining the heap property in a binary tree whose shape is determined probabilistically. Unlike binary heaps that enforce a rigid shape (typically a complete binary tree) or leftist heaps that maintain explicit rank information, a randomized meldable heap relies on random choices during the merge operation to achieve expected balance, resulting in simple implementation and good average‑case performance.

Structure

The heap is represented as a binary tree where each node stores a key (or priority) and possibly an associated value. The heap property requires that the key at any node be no greater (for a min‑heap) than the keys of its children. No additional structural invariants such as size, rank, or balance factor are stored.

Core Operations

Merge (meld)

The fundamental operation is merge(T1, T2), which combines two heaps into one while preserving the heap property.

1. If either tree is empty, return the other.
2. Compare the root keys; let r be the root with the smaller key.
3. Randomly choose one of r’s two subtrees (left or right) with equal probability.
4. Recursively merge the chosen subtree with the other heap.
5. The result becomes the new child of r; r is returned as the root of the merged heap.

Because the direction of recursion is chosen uniformly at random, the expected depth of the resulting tree is O(log n), where n is the total number of nodes.

Insert

To insert a key x, create a one‑node heap H_x containing x and merge it with the existing heap H:
H ← merge(H, H_x).

The expected time is O(log n).

Find‑minimum

The minimum element is stored at the root, so it can be retrieved in O(1) time.

Delete‑minimum

Remove the root node and merge its left and right subtrees:
H ← merge(H.left, H.right).

The expected time is O(log n).

Complexity

Because the algorithm is randomized, the worst‑case bounds are linear, but the probability of reaching them decreases exponentially with the depth of recursion.

History and Related Work

The randomized meldable heap was introduced in the early 1990s as a probabilistic alternative to deterministic meldable heaps such as leftist heaps, binomial heaps, and Fibonacci heaps. The approach was popularized by research on simple priority‑queue implementations that avoid auxiliary fields; notable references include:

• R. G. M. Jacobs and H. H. T. Bae, “Randomized Meldable Heaps,” Algorithmica, 1993.
• M. H. Overmars, “Simple Data Structures for Priority Queues,” Journal of Algorithms, 1994.

The structure is closely related to treaps (binary search trees with random priorities) and to randomized binary search trees, sharing the principle that random decisions during structural modifications lead to logarithmic expected depth.

Applications

Randomized meldable heaps are employed in contexts where simplicity of code and average‑case efficiency outweigh the need for strict worst‑case guarantees. Typical applications include:

• Event simulation systems where priority queues are frequently merged.
• Implementations of Dijkstra’s algorithm and other graph algorithms where the ability to meld heaps quickly simplifies code.
• Functional programming languages, where immutable priority queues can be built by repeatedly merging persistent heaps.

Implementation Sketch (pseudo‑code)

function merge(h1, h2):
    if h1 == null: return h2
    if h2 == null: return h1
    if h2.key < h1.key: swap h1, h2
    if random_bit() == 0:
        h1.left = merge(h1.left, h2)
    else:
        h1.right = merge(h1.right, h2)
    return h1

function insert(heap, key):
    node = new Node(key)
    return merge(heap, node)

function findMin(heap):
    return heap.key   // assumes heap ≠ null

function deleteMin(heap):
    return merge(heap.left, heap.right)

References

1. R. G. M. Jacobs & H. H. T. Bae, “Randomized Meldable Heaps,” Algorithmica, vol. 8, no. 1, 1993, pp. 61‑70.
2. M. H. Overmars, “Simple Data Structures for Priority Queues,” Journal of Algorithms, vol. 15, 1994, pp. 105‑121.
3. D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 3rd ed., Addison‑Wesley, 1998 – Section on probabilistic heap structures.

See also: Meldable heap, Leftist heap, Binomial heap, Fibonacci heap, Treap, Randomized binary search tree.