In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, a mergeable heap (also called a meldable heap) is an
abstract data type
In computer science, an abstract data type (ADT) is a mathematical model for data types. An abstract data type is defined by its behavior (Semantics (computer science), semantics) from the point of view of a ''User (computing), user'', of the dat ...
, which is a
heap
Heap or HEAP may refer to:
Computing and mathematics
* Heap (data structure), a data structure commonly used to implement a priority queue
* Heap (mathematics), a generalization of a group
* Heap (programming) (or free store), an area of memory f ...
supporting a merge operation.
Definition
A mergeable heap supports the usual heap operations:
*
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:
[
* ]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):
# x ← Extract-Min(H2)
# while x ≠ Nil
## Insert(H1, x)
## 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
In computer science, a binomial heap is a data structure that acts as a priority queue but also allows pairs of heaps to be merged.
It is important as an implementation of the mergeable heap abstract data type (also called meldable heap), which ...
* Fibonacci heap
In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the binar ...
* Leftist tree
In computer science, a leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node x has an ''s-value'' which is the distance to the nearest leaf node, leaf in subtree rooted at x. In contrast to a ''bin ...
* Pairing heap
A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986.
Pairing heaps are ...
* Skew heap A skew heap (or self-adjusting heap) is a heap data structure implemented as a binary tree. Skew heaps are advantageous because of their ability to merge more quickly than binary heaps. In contrast with binary heaps, there are no structural constra ...
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.
See also
* Addressable heap In computer science, an addressable heap is an abstract data type. Specifically, it is a mergeable heap supporting access to the elements of the heap via handles (also called references). It allows the key of the element referenced by a particular ...
References
{{reflist
Heaps (data structures)