*** Welcome to piglix ***

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:

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.


...
Wikipedia

...