Mergeable heap


In computer science, a mergeable heap is an abstract [data type], which is a heap supporting a merge operation.

Definition

A mergeable heap supports the usual heap operations:Make-Heap, create an empty heap.Insert, insert an element x into the heap H.Min, return the minimum element, or Nil if no such element exists.Extract-Min, extract and return the minimum element, or Nil if no such element exists.
And one more that distinguishes it:Merge, combine the elements of H1 and H2 into a single heap.

Trivial implementation

It is straightforward to implement a mergeable heap given a simple heap:
Merge:
  1. x ← Extract-Min
  2. while x ≠ Nil
  3. # Insert
  4. # x ← Extract-Min
This can however be wasteful as each Extract-Min and Insert typically have to maintain the heap property.

More efficient implementations

Examples of mergeable heap data structures include:
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.