Content deleted Content added
deleting suspicious data from the infobox; please see Talk:Binary heap#O(log n) for decrease-key is misleading Tag: Reverted |
Added missing space complexity - it was not only missing but produced a poorly formatted page. |
||
| (7 intermediate revisions by 6 users not shown) | |||
Line 1:
{{Short description|Variant of heap data structure}}
{{Infobox data structure
| name = Binary (min) heap
| type = binary tree/heap
| invented_by = [[J. W. J. Williams]]
| invented_year = 1964
<!-- NOTE:
For the purposes of "Big O" notation, all bases are equivalent, because changing the base of a log only introduces a constant factor.
Line 10:
DO: O(log n)
DON'T: O(lg n), O(log2 n), O(log_2 n), O(ln n), O(log10 n), etc.
-->| insert_worst = O(log ''n'')▼
| insert_avg = O(1)▼
▲|insert_worst=O(log ''n'')
| delete_min_avg = O(log ''n'')
▲|insert_avg=O(1)
|
|
| decrease_key_worst = O(log ''n'')
|
| find_min_worst = O(1)
|merge_avg=O(''n'')▼
|
| space_avg = O(n)
| space_worst = O(n)
}}
[[File:Max-Heap.svg|thumb|right|Example of a complete binary max-heap]]
[[File:Min-heap.png|thumb|right|Example of a complete binary min heap]]
Line 30 ⟶ 34:
*Inserting an element;
*Removing the smallest or largest element from (respectively) a min-heap or max-heap.
Binary heaps are also commonly employed in the [[heapsort]] [[sorting algorithm]], which is an in-place algorithm
==Heap operations==
Line 48 ⟶ 52:
As an example of binary heap insertion, say we have a max-heap
and we want to add the number 15 to the heap. We first place the 15 in the position marked by the X. However, the heap property is violated since {{nowrap|15 > 8}}, so we need to swap the 15 and the 8. So, we have the heap looking as follows after the first swap:
However the heap property is still violated since {{nowrap|15 > 11}}, so we need to swap again:
which is a valid max-heap. There is no need to check the left child after this final step: at the start, the max-heap was valid, meaning the root was already greater than its left child, so replacing the root with an even greater value will maintain the property that each node is greater than its children ({{nowrap|11 > 5}}; if {{nowrap|15 > 11}}, and {{nowrap|11 > 5}}, then {{nowrap|15 > 5}}, because of the [[transitive relation]]).
Line 70 ⟶ 74:
So, if we have the same max-heap as before
We remove the 11 and replace it with the 4.
Now the heap property is violated since 8 is greater than 4. In this case, swapping the two elements, 4 and 8, is enough to restore the heap property and we need not swap elements further:
The downward-moving node is swapped with the ''larger'' of its children in a max-heap (in a min-heap it would be swapped with its smaller child), until it satisfies the heap property in its new position. This functionality is achieved by the '''Max-Heapify''' function as defined below in [[pseudocode]] for an [[Array data structure|array]]-backed heap ''A'' of length ''length''(''A''). ''A'' is indexed starting at 1.
Line 143 ⟶ 147:
=== Decrease or increase key ===
<!-- section linked from [[Reheapification]] -->
The decrease key operation replaces the value of a node with a given value with a lower value, and the increase key operation does the same but with a higher value. This involves finding the node with the given value, changing the value, and then down-heapifying or up-heapifying to restore the heap property.
Line 238 ⟶ 244:
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örg-Rüdiger Sack|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|author1-link = Jörg-Rüdiger Sack| 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.
Line 247 ⟶ 253:
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
|
| author1-link = Michael D. Atkinson
| author2 = J.-R. Sack
| author2-link = Jörg-Rüdiger Sack
| |||