In computer science, a mergeable heap (also called a meldable heap) is an abstract data type, which is a heap supporting a merge operation.
Contents
Definition
A mergeable heap supports the usual heap operations:
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:
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 ≠ NilInsert(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.
References
Mergeable heap Wikipedia(Text) CC BY-SA