Mergeable heap explained

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 usual heap operations:

And one more that distinguishes it:

Trivial implementation

It is straightforward 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 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.

See also