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