Mergeable heap

In computer science, a mergeable heap (also called a meldable heap) is an abstract data type, which is a heap supporting a merge operation.

Definition

A mergeable heap supports the usual heap operations:

• <code>Make-Heap()</code>, create an empty heap.
• <code>Insert(H,x)</code>, insert an element <code>x</code> into the heap <code>H</code>.
• <code>Min(H)</code>, return the minimum element, or <code>Nil</code> if no such element exists.
• <code>Extract-Min(H)</code>, extract and return the minimum element, or <code>Nil</code> if no such element exists.

And one more that distinguishes it:

• <code>Merge(H1,H2)</code>, combine the elements of <code>H1</code> and <code>H2</code> into a single heap.

Trivial implementation

It is straightforward to implement a mergeable heap given a simple heap:

<code>Merge(H1,H2):</code>

1. <code>x &larr; Extract-Min(H2)</code>
2. <code>while x ≠ Nil</code>
3. <code>Insert(H1, x)</code>
4. <code>x &larr; Extract-Min(H2)</code>

This can however be wasteful as each <code>Extract-Min(H)</code> and <code>Insert(H,x)</code> typically have to maintain the heap property.

More efficient implementations

Examples of mergeable heap data structures include:

• Binomial heap
• Fibonacci heap
• Leftist tree
• Pairing heap
• Skew heap

A more complete list with performance comparisons can be found at .

In most mergeable heap structures, merging is the fundamental operation on which others are based. Insertion is implemented by merging a new single-element heap with the existing heap. Deletion is implemented by merging the children of the deleted node.

See also

• Addressable heap

References