Jump to content

Mergeable heap

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Bcnof (talk | contribs) at 18:57, 28 May 2015 (→‎More efficient implementations). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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]

  • Make-Heap(), creating an empty heap.
  • Insert(H,x), inserting an element x into the heap H.
  • Min(H), returning the minimum element, or Nil if no such element exists.
  • Extract-Min(H), extracting and returning the minimum element, or Nil if no such element exists.
  • Merge(H1,H2), combining the elements of H1 and H2.

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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Mergeable_heap&oldid=664454951"