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]
-
Make-Heap()
, creating an empty heap. -
Insert(H,x)
, inserting an elementx
into the heapH
. -
Min(H)
, returning the minimum element, orNil
if no such element exists. -
Extract-Min(H)
, extracting and returning the minimum element, orNil
if no such element exists. -
Merge(H1,H2)
, combining the elements ofH1
andH2
.
Trivial implementation
It is straightforward to implement a mergeable heap given a simple heap:
Merge(H1,H2):
-
x ← Extract-Min(H2)
-
while x ≠ Nil
-
Insert(H1, x)
-
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
- ↑ 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.