mergeable heap

A mergeable heap supports the usual heap operations:{{Introduction to Algorithms|3|pages=505–506}}

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

And one more that distinguishes it:

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

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

Merge(H1,H2):

1. x ← Extract-Min(H2)
2. while x ≠ Nil
3. Insert(H1, x)
4. x ← Extract-Min(H2)

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

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 {{slink|Heap (data structure)|Comparison of theoretic bounds for variants}}.

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.

• Addressable heap

{{reflist}}

Category:Heaps (data structures)