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 usual heap operations:
And one more that distinguishes it:
Trivial implementation.
It is straightforward to implement a mergeable heap given a simple heap:
codice_12
This can however be wasteful as each codice_7 and codice_2 typically have to maintain the heap property.
More efficient implementations.
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.