Heap (data structure)

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)

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

Comparison of theoretic bounds for variants

Function names assume a min-heap:

Operation	Binary	Binomial	Fibonacci		Pairing		Leftist
Operation	worst-case	worst-case	amortized	worst-case	amortized	worst-case	worst-case
find-min	O $(1)$	O $(\log n)$	O $(1)$	O $(1)$	O $(1)$	O $(1)$	O $(1)$
delete-min	O $(\log n)$	O $(\log n)$	O $(\log n)$	O $(n)$	O $(\log n)$	O $(n)$	O $(\log n)$
insert	O $(\log n)$	O $(\log n)$	O $(1)$	O $(1)$	O $(1)$ or O $(\log n)$	O $(1)$	O $(\log n)$
decrease-key	O $(\log n)$	O $(\log n)$	O $(1)$	O $(1)$	O $(1)$ or O $(\log n)$	O $(1)$	O $(\log n)$
merge	O $(n)$	O $(\log n)$	O $(1)$	O $(1)$	O $(1)$ or O $(\log n)$	O $(1)$	O $(\log n)$

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 heap over tree in some applications is construction of heap 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.

External links

Priority Queues by Lee Killough

Data structures | Trees (structure)