In computer science, a mergeable heap (also called a meldable heap) is an abstract data type, which is a heap supporting a merge operation.
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.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.
Examples of mergeable heap data structures include:
A more complete list with performance comparisons can be found at .
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.