Editing Binary heap (section)

==Heap operations==
Both the insert and remove operations modify the heap to preserve the shape property first, by adding or removing from the end of the heap. Then the heap property is restored by traversing up or down the heap. Both operations take {{nowrap|O(log ''n'')}} time.

=== Insert ===
To insert an element to a heap, we perform the following steps:

# Add the element to the bottom level of the heap at the leftmost open space.
# Compare the added element with its parent; if they are in the correct order, stop.
# If not, swap the element with its parent and return to the previous step.

Steps 2 and 3, which restore the heap property by comparing and possibly swapping a node with its parent, are called ''the up-heap'' operation (also known as ''bubble-up'', ''percolate-up'', <!-- not a typo: -->''sift-up'', ''trickle-up'', ''swim-up'', ''heapify-up'', ''cascade-up'', or ''fix-up'').

The number of operations required depends only on the number of levels the new element must rise to satisfy the heap property. Thus, the insertion operation has a worst-case time complexity of {{nowrap|O(log ''n'')}}. For a random heap, and for repeated insertions, the insertion operation has an average-case complexity of O(1).<ref>{{Cite journal|last1=Porter|first1=Thomas|last2=Simon|first2=Istvan|date=Sep 1975|title=Random insertion into a priority queue structure|journal=IEEE Transactions on Software Engineering|volume=SE-1|issue=3|pages=292–298|doi=10.1109/TSE.1975.6312854|s2cid=18907513|issn=1939-3520}}</ref><ref>{{Cite journal |last1=Mehlhorn|first1=Kurt|last2=Tsakalidis|first2=A.|date=Feb 1989| title=Data structures |website=Universität des Saarlandes |url=https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/26179 |language=en|page=27|doi=10.22028/D291-26123 |quote=Porter and Simon [171] analyzed the average cost of inserting a random element into a random heap in terms of exchanges. They proved that this average is bounded by the constant 1.61. Their proof docs not generalize to sequences of insertions since random insertions into random heaps do not create random heaps. The repeated insertion problem was solved by Bollobas and Simon [27]; they show that the expected number of exchanges is bounded by 1.7645. The worst-case cost of inserts and deletemins was studied by Gonnet and Munro [84]; they give log log n + O(1) and log n + log n* + O(1) bounds for the number of comparisons respectively.}}</ref>

As an example of binary heap insertion, say we have a max-heap

[[File:Heap add step1.svg|150px|class=skin-invert-image]]

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:

[[File:Heap add step2.svg|150px|class=skin-invert-image]]

However the heap property is still violated since {{nowrap|15 > 11}}, so we need to swap again:

[[File:Heap add step3.svg|150px|class=skin-invert-image]]

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]]).

=== Extract===
The procedure for deleting the root from the heap (effectively extracting the maximum element in a max-heap or the minimum element in a min-heap) while retaining the heap property is as follows:

#Replace the root of the heap with the last element on the last level.
#Compare the new root with its children; if they are in the correct order, stop.
#If not, swap the element with one of its children and return to the previous step. (Swap with its smaller child in a min-heap and its larger child in a max-heap.)
Steps 2 and 3, which restore the heap property by comparing and possibly swapping a node with one of its children, are called the ''down-heap'' (also known as ''bubble-down'', ''percolate-down'', <!-- not a typo: -->''sift-down'', ''sink-down'', ''trickle down'', ''heapify-down'', ''cascade-down'', ''fix-down'', ''extract-min'' or ''extract-max'', or simply ''heapify'') operation.

So, if we have the same max-heap as before

[[File:Heap delete step0.svg|150px|class=skin-invert-image]]

We remove the 11 and replace it with the 4.

[[File:Heap remove step1.svg|150px|class=skin-invert-image]]

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:

[[File:Heap remove step2.svg|150px|class=skin-invert-image]]

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.

 // Perform a down-heap or heapify-down operation for a max-heap
 // ''A'': an array representing the heap, indexed starting at 1
 // ''i'': the index to start at when heapifying down
 '''Max-Heapify'''(''A'', ''i''):
     ''left'' ← 2×''i''
     ''right'' ← 2×''i'' + 1
     ''largest'' ← ''i''
     
     '''if''' ''left'' ≤ ''length''(''A'') '''and''' ''A''[''left''] > A[''largest''] '''then''':
         ''largest'' ← ''left''<br />
     '''if''' ''right'' ≤ ''length''(''A'') '''and''' ''A''[''right''] > ''A''[''largest''] '''then''':
         ''largest'' ← ''right''
     
     '''if''' ''largest'' ≠ ''i'' '''then''':
         '''swap''' ''A''[''i''] and ''A''[''largest'']
         '''Max-Heapify'''(''A'', ''largest'')

For the above algorithm to correctly re-heapify the array, no nodes besides the node at index ''i'' and its two direct children can violate the heap property. The down-heap operation (without the preceding swap) can also be used to modify the value of the root, even when an element is not being deleted.

In the worst case, the new root has to be swapped with its child on each level until it reaches the bottom level of the heap, meaning that the delete operation has a time complexity relative to the height of the tree, or O(log ''n'').

=== Insert then extract ===
Inserting an element then extracting from the heap can be done more efficiently than simply calling the insert and extract functions defined above, which would involve both an <code>upheap</code> and <code>downheap</code> operation. Instead, we can do just a <code>downheap</code> operation, as follows:

# Compare whether the item we're pushing or the peeked top of the heap is greater (assuming a max heap)
# If the root of the heap is greater:
## Replace the root with the new item
## Down-heapify starting from the root
# Else, return the item we're pushing

[[Python (programming language)|Python]] provides such a function for insertion then extraction called "heappushpop", which is paraphrased below.<ref>{{Cite web| title=python/cpython/heapq.py| url=https://github.com/python/cpython/blob/master/Lib/heapq.py|access-date=2020-08-07| website=GitHub| language=en}}</ref><ref>{{Cite web|title=heapq — Heap queue algorithm — Python 3.8.5 documentation| url=https://docs.python.org/3/library/heapq.html#heapq.heappushpop|access-date=2020-08-07| website=docs.python.org|quote=heapq.heappushpop(heap, item): Push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush() followed by a separate call to heappop().}}</ref> The heap array is assumed to have its first element at index 1.
 // Push a new item to a (max) heap and then extract the root of the resulting heap. 
 // ''heap'': an array representing the heap, indexed at 1
 // ''item'': an element to insert
 // Returns the greater of the two between ''item'' and the root of ''heap''.
 '''Push-Pop'''(''heap'': List<T>, ''item'': T) -> T:
     '''if''' ''heap'' is not empty '''and''' heap[1] > ''item'' '''then''':  // < if min heap
         '''swap''' ''heap''[1] and ''item''
         _downheap(''heap'' starting from index 1)
     '''return''' ''item''
A similar function can be defined for popping and then inserting, which in Python is called "heapreplace":
 // Extract the root of the heap, and push a new item 
 // ''heap'': an array representing the heap, indexed at 1
 // ''item'': an element to insert
 // Returns the current root of ''heap''
 '''Replace'''(''heap'': List<T>, ''item'': T) -> T:
     '''swap''' ''heap''[1] and ''item''
     _downheap(''heap'' starting from index 1)
     '''return''' ''item''

=== Search ===
Finding an arbitrary element takes O(n) time.

=== Delete ===
Deleting an arbitrary element can be done as follows:

# Find the index <math>i</math> of the element we want to delete
# Swap this element with the last element. Remove the last element after the swap.
# Down-heapify or up-heapify to restore the heap property. In a max-heap (min-heap), up-heapify is only required when the new key of element <math>i</math> is greater (smaller) than the previous one because only the heap-property of the parent element might be violated. Assuming that the heap-property was valid between element <math>i</math> and its children before the element swap, it can't be violated by a now larger (smaller) key value. When the new key is less (greater) than the previous one then only a down-heapify is required because the heap-property might only be violated in the child elements.

=== 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.

Decrease key can be done as follows:

# Find the index of the element we want to modify
# Decrease the value of the node
# Down-heapify (assuming a max heap) to restore the heap property

Increase key can be done as follows:

# Find the index of the element we want to modify
# Increase the value of the node
# Up-heapify (assuming a max heap) to restore the heap property