In computer science, a heap is a specialized tree-based data structure that satisfies the heap property. Its base datatype (used for node keys) must be an ordered set.

If B is a child node of A, then the heap property is that:

: key(A) ≥ key(B)

thumb

This implies that the greatest element is always in the root node, and such a heap is sometimes called a max heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min heap.) This is why heaps are used to implement priority queues. The efficiency of heap operations is crucial in several graph algorithms.

The operations commonly performed with a heap are
* delete-max or delete-min: removing the root node of a max- or min-heap, respectively
* decrease-key: updating a key within the heap
* insert: adding a new key to the heap
* merge: joining two heaps to form a valid new heap containing all the elements of both.

Heaps are used in the sorting algorithm called heapsort.

Variants

* Binary heap
* Binomial heap
* Fibonacci heap
* Pairing heap
* Leftist heap
* Soft heap
* 2-3 heap
* Treap
* Beap
* Skew heap

Comparison of theoretic bounds for variants

Function names assume a min-heap:

For pairing heaps the insert, decreaseKey and merge operations are conjectured to be O$(1)$ amortized complexity but this has not yet been proven.

Heap applications

Heaps are favourite data structures for many applications.
* Heap sort: One of the best sorting methods being in-place and with no quadratic worst case scenarios.
* Selection algorithms: Finding the min, max or both of them, median or even any k-th element in sublinear time can be done dynamically with heaps.
* Graph algorithms: By using heaps as internal traversal data structures, run time will be reduced by an order of polynomial. Examples of such problems are Kruskal's minimal spanning tree algorithm and Dijkstra's shortest path problem.

One more advantage of heaps over trees in some applications is that construction of heaps can be done in linear time using Tarjan's algorithm.

Heap implementations

*The Silicon Graphics implementation of the C++ Standard Template Library provides the make_heap, push_heap and pop_heap algorithms for binary heaps, which operate on arbitrary random access iterators. Interestingly, push_heap does not actually add an element to the sequence but instead restores heap structure by swapping elements (if necessary) after a new element has been added to the end of the sequence. Likewise, pop_heap moves the removed element to the end of the sequence.

Build Heap

A procedure that changes an already existing heap so that the heap maintains the heap property. The time of this algorithm is O(n) on an array-based heap implementation, where n is the number of nodes in the heap.

See also

*Heaps at Wikiversity
*Heaps at wikibooks

External links

*Priority Queues by Lee Killough

Category:Trees (structure)