Agfdhyk

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:^[1]

• 
  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:^[1]

• 
  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):

1. x ← Extract-Min(H2)


2. 
   while x ≠ Nil
   
   
   
   1. Insert(H1, x)
   
   
   2. 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 heap data structures include:

• Binomial heap


• Fibonacci heap


• Leftist tree


• Pairing heap


• Skew heap

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, mergeing 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.

See also

• Addressable heap

References