Editing Heap (data structure) (section)

==Applications==
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 algorithm]]s: 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.<ref>{{citation
 | last = Frederickson
 | first = Greg N.
 | contribution = An Optimal Algorithm for Selection in a Min-Heap
 | doi = 10.1006/inco.1993.1030
 | pages = 197–214
 | publisher = Academic Press
 | title = Information and Computation
 | volume = 104
 | issue = 2
 | year = 1993
 | url = http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf
 | access-date = 2010-10-31
 | archive-url = https://web.archive.org/web/20121203045606/http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf
 | archive-date = 2012-12-03
 | url-status = dead
 | doi-access = free
 }}</ref>
* [[List of algorithms#Graph algorithms|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 algorithm|Prim's minimal-spanning-tree algorithm]] and [[Dijkstra's algorithm|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 algorithm|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.)