Editing Binary heap (section)

{{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.
Since the base of logarithms doesn't matter, please do not write complexity expressions that indicate base-2 (or any other base).
   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)
|delete_min_avg=O(log ''n'')
|delete_min_worst=O(log ''n'')
|decrease_key_avg=O(log ''n'')
|decrease_key_worst=O(log ''n'')
|find_min_avg=O(1)
|find_min_worst=O(1)
|merge_avg=O(''n'')
|merge_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]]
A '''binary heap''' is a [[heap (data structure)|heap]] [[data structure]] that takes the form of a [[binary tree]]. Binary heaps are a common way of implementing [[priority queue]]s.{{r|clrs|pp=162–163}} The binary heap was introduced by [[J. W. J. Williams]] in 1964 as a data structure for implementing [[heapsort]].<ref>{{Citation |first=J. W. J. |last=Williams |author-link=J. W. J. Williams |title=Algorithm 232 - Heapsort |year=1964 |journal=[[Communications of the ACM]] |volume=7 |issue=6 |pages=347–348 |doi= 10.1145/512274.512284}}</ref>

A binary heap is defined as a binary tree with two additional constraints:<ref>{{citation | author=Y Narahari | title=Data Structures and Algorithms | chapter=Binary Heaps | url=https://gtl.csa.iisc.ac.in/dsa/ | chapter-url=http://lcm.csa.iisc.ernet.in/dsa/node137.html}}</ref>
*Shape property: a binary heap is a ''[[complete binary tree]]''; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
*Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node's children, according to some [[total order]].

Heaps where the parent key is greater than or equal to (≥) the child keys are called ''max-heaps''; those where it is less than or equal to (≤) are called ''min-heaps''. Efficient (that is, [[logarithmic time]]) algorithms are known for the two operations needed to implement a priority queue on a binary heap:
*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 as binary heaps can be implemented as an [[implicit data structure]], storing keys in an array and using their relative positions within that array to represent child–parent relationships.