The heap is one maximally efficient implementation of an abstract data type called a priority queue, and in fact, priority queues are often referred to as "heaps", regardless of how they may be implemented. In a heap, the highest (or lowest) priority element is always stored at the root. However, a heap is not a sorted structure; it can be regarded as being partially ordered. A heap is a useful data structure when it is necessary to repeatedly remove the object with the highest (or lowest) priority.
A common implementation of a heap is the binary heap, in which the tree is a binary tree The heap data structure, specifically the binary heap, was introduced by J. W. J. Williams in 1964, as a data structure for the heapsort sorting algorithm. Heaps are also useful in several efficient graph algorithms such as Dijkstra's algorithm. When a heap is a complete binary tree, it has a smallest possible height a heap with N nodes and for each node a branches always has loga N height.
The common operations involving heaps are:
-> find-max (or find-min): find a maximum item of a max-heap, or a minimum item of a min-heap, respectively.
insert: adding a new key to the heap.
-> extract-max (or extract-min): returns the node of maximum value from a max heap [or minimum value from a min heap] after removing it from the heap.
-> delete-max (or delete-min): removing the root node of a max heap (or min heap), respectively
-> replace: pop root and push a new key. More efficient than pop followed by push, since only need to balance once, not twice, and appropriate for fixed-size heaps.
-> create-heap: create an empty heap.
-> heapify: create a heap out of the given array of elements
-> merge (union): joining two heaps to form a valid new heap containing all the elements of both, preserving the original heaps.
-> meld: joining two heaps to form a valid new heap containing all the elements of both, destroying the original heaps.
-> size: return the number of items in the heap.
-> is-empty: return true if the heap is empty, false otherwise.
-> increase-key or decrease-key: updating a key within a max- or min-heap, respectively
-> delete: delete an arbitrary node (followed by moving last node and sifting to maintain heap)
-> sift-up: move a node up in the tree, as long as needed; used to restore heap condition after insertion. Called "sift" because node moves up the tree until it reaches the correct level, as in a sieve.
-> sift-down: move a node down in the tree, similar to sift-up; used to restore heap condition after deletion or replacement.
Heaps are basically of two types.
Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.
Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.
The heap data structure has many applications.
Heapsort: One of the best sorting methods being in-place and with no quadratic worst-case scenarios.
Selection algorithms: A heap allows access to the min or max element in constant time, and other selections (such as median or kth-element) can be done in sub-linear time on data that is in a heap.
Graph algorithms: By using heaps as internal traversal data structures, run time will be reduced by polynomial order. Examples of such problems are Prim's minimal-spanning-tree algorithm and Dijkstra's shortest-path algorithm.
Priority Queue: A priority queue is an abstract concept like "a list" or "a map"; just as a list can be
implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods.
K-way merge: A heap data structure is useful to merge many already-sorted input streams into a single sorted output stream. Examples of the need for merging include external sorting and streaming results from distributed data such as a log structured merge tree. The inner loop is obtaining the min element, replacing with the next element for the corresponding input stream, then doing a sift-down heap operation. (Alternatively, the replace function.) (Using extract-max and insert functions of a priority queue are much less efficient.)
Order statistics: The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array.