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.

A mergeable heap supports the usual heap operations:[1] And one more that distinguishes it:[1] 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 heap data structures include: A more complete list with performance comparisons can be found at Heap (data structure) § Comparison of theoretic bounds for variants.

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.