Mergeable heap

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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:^[1]

Make-Heap(), create an empty heap.
Insert(H,x), insert an element x into the heap H.
Min(H), return the minimum element, or Nil if no such element exists.
Extract-Min(H), extract and return the minimum element, or Nil if no such element exists.

And one more that distinguishes it:^[1]

Merge(H1,H2), 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(H1,H2):

x ← Extract-Min(H2)
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 Heap (data structure) § Comparison of theoretic bounds for variants.

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.

References

^ ^a ^b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 505–506. ISBN 0-262-03384-4.

[CLR-1] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 505–506. ISBN 0-262-03384-4.

[1]

Definition

Trivial implementation

More efficient implementations

See also

References