Editing Heapsort (section)

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