Editing Binary heap (section)

== Heap implementation ==<!-- This section is linked from [[Heapsort]] -->
[[File:Binary tree in array.svg|right|frame|A small complete binary tree stored in an array]]
[[File:Binary Heap with Array Implementation.JPG|400px|thumb|right|Comparison between a binary heap and an array implementation.]]

Heaps are commonly implemented with an [[Array data structure|array]]. Any binary tree can be stored in an array, but because a binary heap is always a complete binary tree, it can be stored compactly. No space is required for [[pointer (computer programming)|pointer]]s; instead, the parent and children of each node can be found by arithmetic on array indices. These properties make this heap implementation a simple example of an [[implicit data structure]] or [[Ahnentafel]] list. Details depend on the root position, which in turn may depend on constraints of a [[programming language]] used for implementation, or programmer preference. Specifically, sometimes the root is placed at index 1, in order to simplify arithmetic.

Let ''n'' be the number of elements in the heap and ''i'' be an arbitrary valid index of the array storing the heap. If the tree root is at index 0, with valid indices 0 through ''n − ''1, then each element ''a'' at index ''i'' has
* children at indices 2''i ''+ 1 and 2''i ''+ 2
* its parent at index ''[[floor function|floor]]''((''i'' &minus; 1) / 2).
Alternatively, if the tree root is at index 1, with valid indices 1 through ''n'', then each element ''a'' at index ''i'' has
* children at indices 2''i'' and 2''i ''+1
* its parent at index ''[[floor function|floor]]''(''i'' / 2).

This implementation is used in the [[heapsort]] algorithm which reuses the space allocated to the input array to store the heap (i.e. the algorithm is done [[In-place algorithm|in-place]]). This implementation is also useful as a [[Priority queue]].  When a [[dynamic array]] is used, insertion of an unbounded number of items is possible.

The <code>upheap</code> or <code>downheap</code> operations can then be stated in terms of an array as follows: suppose that the heap property holds for the indices ''b'', ''b''+1, ..., ''e''. The sift-down function extends the heap property to ''b''−1, ''b'', ''b''+1, ..., ''e''.
Only index ''i'' = ''b''−1 can violate the heap property.
Let ''j'' be the index of the largest child of ''a''[''i''] (for a max-heap, or the smallest child for a min-heap) within the range ''b'', ..., ''e''.
(If no such index exists because {{nowrap|2''i'' > ''e''}} then the heap property holds for the newly extended range and nothing needs to be done.)
By swapping the values ''a''[''i''] and ''a''[''j''] the heap property for position ''i'' is established.
At this point, the only problem is that the heap property might not hold for index ''j''.
The sift-down function is applied [[tail recursion|tail-recursively]] to index ''j'' until the heap property is established for all elements.

The sift-down function is fast. In each step it only needs two comparisons and one swap. The index value where it is working doubles in each iteration, so that at most log<sub>2</sub> ''e'' steps are required.

For big heaps and using [[virtual memory]], storing elements in an array according to the above scheme is inefficient: (almost) every level is in a different [[Page (computer memory)|page]].  [[B-heap]]s are binary heaps that keep subtrees in a single page, reducing the number of pages accessed by up to a factor of ten.<ref>{{cite magazine|first = Poul-Henning|last= Kamp|url = http://queue.acm.org/detail.cfm?id=1814327 |title = You're Doing It Wrong|magazine= ACM Queue|date = June 11, 2010|volume = 8|issue = 6}}
</ref>

The operation of merging two binary heaps takes Θ(''n'') for equal-sized heaps. The best you can do is (in case of array implementation) simply concatenating the two heap arrays and build a heap of the result.<ref>Chris L. Kuszmaul.
[http://nist.gov/dads/HTML/binaryheap.html "binary heap"] {{Webarchive| url=https://web.archive.org/web/20080808141408/http://www.nist.gov/dads/HTML/binaryheap.html |date=2008-08-08 }}.
Dictionary of Algorithms and Data Structures, Paul E. Black, ed., U.S. National Institute of Standards and Technology. 16 November 2009.</ref> A heap on ''n'' elements can be merged with a heap on ''k'' elements using O(log ''n'' log ''k'') key comparisons, or, in case of a pointer-based implementation, in O(log ''n'' log ''k'') time.<ref>J.-R. Sack and T. Strothotte
[https://doi.org/10.1007%2FBF00264229 "An Algorithm for Merging Heaps"],
Acta Informatica 22, 171-186 (1985).</ref> An algorithm for splitting a heap on ''n'' elements into two heaps on ''k'' and ''n-k'' elements, respectively, based on a new view
of heaps as an ordered collections of subheaps was presented in.<ref>{{Cite journal |doi = 10.1016/0890-5401(90)90026-E|title = A characterization of heaps and its applications|journal = Information and Computation|volume = 86|pages = 69–86|year = 1990|last1 = Sack|first1 = Jörg-Rüdiger| last2 = Strothotte|first2 = Thomas|doi-access = free}}</ref> The algorithm requires O(log ''n'' * log ''n'')  comparisons. The view also presents a new and conceptually simple algorithm for merging heaps. When merging is a common task, a different heap implementation is recommended, such as [[binomial heap]]s, which can be merged in O(log ''n'').

Additionally, a binary heap can be implemented with a traditional binary tree data structure, but there is an issue with finding the adjacent element on the last level on the binary heap when adding an element. This element can be determined algorithmically or by adding extra data to the nodes, called "threading" the tree—instead of merely storing references to the children, we store the [[inorder]] successor of the node as well.

It is possible to modify the heap structure to make the extraction of both the smallest and largest element possible in [[Big O notation|<math>O</math>]]<math>(\log n)</math> time.<ref name="sym">{{cite web
| url = http://cg.scs.carleton.ca/~morin/teaching/5408/refs/minmax.pdf
| author = Atkinson, M.D.
| author2 = J.-R. Sack
| author2-link = Jörg-Rüdiger Sack
| author3 = N. Santoro
| author4 = T. Strothotte
| name-list-style = amp
| title = Min-max heaps and generalized priority queues.
| publisher = Programming techniques and Data structures. Comm. ACM, 29(10): 996–1000
| date = 1 October 1986
| access-date = 29 April 2008
| archive-date = 27 January 2007
| archive-url = https://web.archive.org/web/20070127093845/http://cg.scs.carleton.ca/%7Emorin/teaching/5408/refs/minmax.pdf
| url-status = dead
}}</ref>  To do this, the rows alternate between min heap and max-heap.  The algorithms are roughly the same, but, in each step, one must consider the alternating rows with alternating comparisons.  The performance is roughly the same as a normal single direction heap. This idea can be generalized to a min-max-median heap.