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:
And one more that distinguishes it:
It is straightforward to implement a mergeable heap given a simple heap:
Merge(H1,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 heaps include:
A more complete list with performance comparisons can be found here.