Editing Heapsort (section)

== Algorithm ==
The heapsort algorithm begins by rearranging the array into a binary max-heap. The algorithm then repeatedly swaps the root of the heap (the greatest element remaining in the heap) with its last element, which is then declared to be part of the sorted suffix.  Then the heap, which was damaged by replacing the root, is repaired so that the greatest element is again at the root. This repeats until only one value remains in the heap.

The steps are:
# Call the {{code|heapify()}} function on the array. This builds a heap from an array in {{math|''O''(''n'')}} operations.
# Swap the first element of the array (the largest element in the heap) with the final element of the heap.  Decrease the considered range of the heap by one.
# Call the {{code|siftDown()}} function on the array to move the new first element to its correct place in the heap.
# Go back to step (2) until the remaining array is a single element.
The {{code|heapify()}} operation is run once, and is {{math|''O''(''n'')}} in performance. The {{code|siftDown()}} function is called {{mvar|n}} times and requires {{math|''O''(log ''n'')}} work each time, due to its traversal starting from the root node.  Therefore, the performance of this algorithm is {{math|1=''O''(''n'' + ''n'' log ''n'') = ''O''(''n'' log ''n'')}}.

The heart of the algorithm is the {{code|siftDown()}} function.  This constructs binary heaps out of smaller heaps, and may be thought of in two equivalent ways:
* given two binary heaps, and a shared parent node which is not part of either heap, merge them into a single larger binary heap; or
* given a "damaged" binary heap, where the max-heap property (no child is greater than its parent) holds everywhere ''except'' possibly between the root node and its children, repair it to produce an undamaged heap.

To establish the max-heap property at the root, up to three nodes must be compared (the root and its two children), and the greatest must be made the root.  This is most easily done by finding the greatest child, then comparing that child to the root.  There are three cases:
# If there are no children (the two original heaps are empty), the heap property trivially holds, and no further action is required.
# If root is greater than or equal to the greatest child, the heap property holds and likewise, no further action is required.
# If the root is less than the greatest child, exchange the two nodes.  The heap property now holds at the newly promoted node (it is greater than or equal to both of its children, and in fact greater than any descendant), but may be violated between the newly demoted ex-root and its new children.  To correct this, repeat the {{code|siftDown()}} operation on the subtree rooted at the newly demoted ex-root.

The number of iterations in any one {{code|siftdown()}} call is bounded by the height of the tree, which is {{math|1={{floor|log{{sub|2}} ''n''}} = ''O''(log ''n'')}}.

=== Pseudocode ===

The following is a simple way to implement the algorithm in [[pseudocode]]. Arrays are [[Comparison of programming languages (array)|zero-based]] and {{code|swap}} is used to exchange two elements of the array. Movement 'down' means from the root towards the leaves, or from lower indices to higher. Note that during the sort, the largest element is at the root of the heap at {{code|a[0]}}, while at the end of the sort, the largest element is in {{code|a[end]}}.

 '''procedure''' heapsort(a, count) '''is'''
     '''input:''' an unordered array ''a'' of length ''count''
  
     ''(Build the heap in array a so that largest value is at the root)''
     heapify(a, count)
 
     ''(The following loop maintains the [[Loop invariant|invariants]] that a[0:end−1] is a heap, and''
     ''every element a[end:count−1] beyond end is greater than everything before it,''
     ''i.e. a[end:count−1] is in sorted order.)''
     end ← count
     '''while''' end > 1 '''do'''
         ''(the heap size is reduced by one)''
         end ← end − 1
         ''(a[0] is the root and largest value. The swap moves it in front of the sorted elements.)''
         swap(a[end], a[0])
         ''(the swap ruined the heap property, so restore it)''
         siftDown(a, 0, end)

The sorting routine uses two subroutines, {{code|heapify}} and {{code|siftDown}}. The former is the common in-place heap construction routine, while the latter is a common subroutine for implementing {{code|heapify}}.
 
 ''(Put elements of 'a' in heap order, in-place)''
 '''procedure''' heapify(a, count) '''is'''
     ''(start is initialized to the first leaf node)''
     ''(the last element in a 0-based array is at index count-1; find the parent of that element)''
     start ← iParent(count-1) + 1
     
     '''while''' start > 0 '''do'''
         ''(go to the last non-heap node)''
         start ← start − 1
         ''(sift down the node at index 'start' to the proper place such that all nodes below''
         '' the start index are in heap order)''
         siftDown(a, start, count)
     ''(after sifting down the root all nodes/elements are in heap order)''
     
 ''(Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid)''
 '''procedure''' siftDown(a, root, end) '''is'''
     '''while''' iLeftChild(root) < end '''do'''    ''(While the root has at least one child)''
         child ← iLeftChild(root)       ''(Left child of root)''
         ''(If there is a right child and that child is greater)''
         '''if''' child+1 < end '''and''' a[child] < a[child+1] '''then'''
             child ← child + 1
     
         '''if''' a[root] < a[child] '''then'''
             swap(a[root], a[child])
             root ← child         ''(repeat to continue sifting down the child now)''
         '''else'''
             ''(The root holds the largest element. Since we may assume the heaps rooted''
             '' at the children are valid, this means that we are done.)''
             '''return'''

The {{code|heapify}} procedure operates by building small heaps and repeatedly merging them using {{code|siftDown}}.  It starts with the leaves, observing that they are trivial but valid heaps by themselves, and then adds parents.  Starting with element {{math|''n''/2}} and working backwards, each internal node is made the root of a valid heap by sifting down. The last step is sifting down the first element, after which the entire array obeys the heap property.

To see that this takes {{math|''O''(''n'')}} time, count the worst-case number of {{code|siftDown}} iterations.  The last half of the array requires zero iterations, the preceding quarter requires at most one iteration, the eighth before that requires at most two iterations, the sixteenth before that requires at most three, and so on.

Looked at a different way, if we assume every {{code|siftDown}} call requires the maximum number of iterations, the first half of the array requires one iteration, the first quarter requires one more (total 2), the first eighth requires yet another (total 3), and so on.

This totals {{math|1=''n''/2 + ''n''/4 + ''n''/8 + ⋯ = n⋅(1/2 + 1/4 + 1/8 + ⋯)}}, where the infinite sum is a well-known [[geometric series]] whose sum is {{math|1}}, thus the product is simply {{mvar|n}}.

The above is an approximation.  The exact worst-case number of comparisons during the heap-construction phase of heapsort is known to be equal to {{math|2''n'' − 2''s''<sub>2</sub>(''n'') − ''e''<sub>2</sub>(''n'')}}, where {{math|''s''<sub>2</sub>(''n'')}} is the [[Hamming weight|number of 1 bits]] in the binary representation of {{mvar|n}} and {{math|''e''<sub>2</sub>(''n'')}} is the [[Find first set|number of trailing 0 bits]].<ref>{{cite journal
 | last1 = Suchenek | first1 = Marek A.
 | title = Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program
 | doi = 10.3233/FI-2012-751
 | pages = 75–92
 | journal = [[Fundamenta Informaticae]]
 | volume = 120
 | issue = 1
 | year = 2012}}</ref><ref>{{cite arXiv
	| last = Suchenek | first = Marek A.
	| title = A Complete Worst-Case Analysis of Heapsort with Experimental Verification of Its Results, A manuscript
	| date = 2015-04-07
	| eprint = 1504.01459
	| class = cs.DS
}}</ref>

=== Standard implementation ===
Although it is convenient to think of the two phases separately, most implementations combine the two, allowing a single instance of {{code|siftDown}}to be [[Inline expansion|expanded inline]].<ref>{{harvnb|Knuth|1997}}</ref>{{rp|Algorithm H}}  Two variables (here, {{code|start}} and {{code|end}}) keep track of the bounds of the heap area.  The portion of the array before {{code|start}} is unsorted, while the portion beginning at {{code|end}} is sorted.  Heap construction decreases {{code|start}} until it is zero, after which heap extraction decreases {{code|end}} until it is 1 and the array is entirely sorted.

 '''procedure''' heapsort(a, count) '''is'''
     '''input:''' an unordered array ''a'' of length ''count''
     
     start ← floor(count/2)
     end ← count
     '''while''' end > 1 '''do'''
         '''if''' start > 0 '''then'''    ''(Heap construction)''
             start ← start − 1
         '''else'''                 ''(Heap extraction)''
             end ← end − 1
             swap(a[end], a[0])
    
         ''(The following is siftDown(a, start, end))''
         root ← start
         '''while''' iLeftChild(root) < end '''do'''
             child ← iLeftChild(root)
             ''(If there is a right child and that child is greater)''
             '''if''' child+1 < end '''and''' a[child] < a[child+1] '''then'''
                 child ← child + 1
     
             '''if''' a[root] < a[child] '''then'''
                 swap(a[root], a[child])
                 root ← child         ''(repeat to continue sifting down the child now)''
             '''else'''
                 '''break'''                ''(return to outer loop)''