Editing Binary heap (section)

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