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 following operations:

• Make-Heap(), creating an empty heap.
• Insert(H,x), inserting an element x into the heap H.
• Min(H), returning the minimum element, or Nil if no such element exists.
• Extract-Min(H), extracting and returning the minimum element, or Nil if no such element exists.
• Merge(H1,H2), creating a new heap combining the elements of H1 and H2.

Trivial implementation

It is straight-forward to implement a mergeable heap given a simple heap:

Merge(H1,H2):

1. x ← Extract-Min(H2)
2. while x ≠ Nil
   1. Insert(H1, x)
   2. 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.

More efficient implementations

Examples of mergeable heaps include:

• Fibonacci heaps
• Binomial heaps
• Pairing heaps
• Binary heaps

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