Editing Heapsort (section)

=== Williams' heap construction ===
{{see also|Binary heap#Building a heap}}
The description above uses Floyd's improved heap-construction algorithm, which operates in {{math|''O''(''n'')}} time and uses the same {{code|siftDown}} primitive as the heap-extraction phase.  Although this algorithm, being both faster and simpler to program, is used by all practical heapsort implementations, Williams' original algorithm may be easier to understand, and is needed to implement a more general binary heap [[priority queue]].

Rather than merging many small heaps, Williams' algorithm maintains one single heap at the front of the array and repeatedly appends an additional element using a {{code|siftUp}} primitive.  Being at the end of the array, the new element is a leaf and has no children to worry about, but may violate the heap property by being greater than its parent.  In this case, exchange it with its parent and repeat the test until the parent is greater or there is no parent (we have reached the root).  In pseudocode, this is:
  
  '''procedure''' siftUp(a, end) '''is'''
      '''input:''' ''a is the array, which heap-ordered up to end-1.''
             ''end is the node to sift up.''
      '''while''' end > 0
          parent := iParent(end)
          '''if''' a[parent] < a[end] '''then''' ''(out of max-heap order)''
              swap(a[parent], a[end])
              end := parent          ''(continue sifting up)''
          '''else'''
              '''return'''
     
  '''procedure''' heapify(a, count) '''is'''
      ''(start with a trivial single-element heap)''
      end := 1
      
      '''while''' end < count
          ''(sift up the node at index end to the proper place such that''
          '' all nodes above the end index are in heap order)''
          siftUp(a, end)
          end := end + 1
      ''(after sifting up the last node all nodes are in heap order)''

[[File:Binary heap bottomup vs topdown.svg|thumb|right|Difference in time complexity between the "siftDown" version and the "siftUp" version.]]
To understand why this algorithm can take asymptotically more time to build a heap ({{math|''O''(''n'' log ''n'')}} vs. {{math|''O''(''n'')}} worst case), note that in Floyd's algorithm, almost all the calls to {{code|siftDown}} operations apply to very ''small'' heaps.  Half the heaps are height-1 trivial heaps and can be skipped entirely, half of the remainder are height-2, and so on.  Only two calls are on heaps of size {{math|''n''/2}}, and only one {{code|siftDown}} operation is done on the full {{mvar|n}}-element heap.  The overall average {{code|siftDown}} operation takes {{math|''O''(1)}} time.

In contrast, in Williams' algorithm most of the calls to {{code|siftUp}} are made on ''large'' heaps of height {{math|''O''(log ''n'')}}.  Half of the calls are made with a heap size of {{math|''n''/2}} or more, three-quarters are made with a heap size of {{math|''n''/4}} or more, and so on.  Although the ''average'' number of steps is similar to Floyd's technique, {{r|Bojesen00|p=3}} pre-sorted input will cause the worst case: each added node is sifted up to the root, so the average call to {{code|siftUp}} will require approximately {{math|1=(log{{sub|2}}''n'' − 1)/2 + (log{{sub|2}}''n'' − 2)/4  + (log{{sub|2}}''n'' − 3)/8 + ⋯}} {{math|1== log{{sub|2}}''n'' − (1 + 1/2 + 1/4 + ⋯)}} {{math|1== log{{sub|2}}''n'' − 2}} iterations.

Because it is dominated by the second heap-extraction phase, the heapsort algorithm itself has {{math|''O''(''n'' log ''n'')}} time complexity using either version of heapify.