Mergeable heap

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

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 heaps include:

A more complete list with performance comparisons can be found here.

See also

References

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. 2009, 3rd ed. The MIT Press. ISBN 978-0-262-53305-8.
This article is issued from Wikipedia - version of the 5/28/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.