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:
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.