Editing Heapsort (section)

=== Bottom-up heapsort ===
Bottom-up heapsort is a variant that reduces the number of comparisons required by a significant factor. While ordinary "top-down" heapsort requires {{math|2''n'' log<sub>2</sub> ''n'' + ''O''(''n'')}} comparisons worst-case and on average,{{r|Wegener}} the bottom-up variant requires {{math|''n'' log<sub>2</sub>''n'' + ''O''(1)}} comparisons on average,{{r|Wegener}} and {{math|1.5''n'' log<sub>2</sub>''n'' + ''O''(''n'')}} in the worst case.{{r|fleischer}}

If comparisons are cheap (e.g. integer keys) then the difference is unimportant,{{r|Melhorn}} as top-down heapsort compares values that have already been loaded from memory. If, however, comparisons require a [[function call]] or other complex logic, then bottom-up heapsort is advantageous.

This is accomplished by using a more elaborate {{code|siftDown}} procedure. The change improves the linear-time heap-building phase slightly,{{r|McDiarmid}} but is more significant in the second phase. Like top-down heapsort, each iteration of the second phase extracts the top of the heap, {{code|a[0]}}, and fills the gap it leaves with {{code|a[end]}}, then sifts this latter element down the heap. But this element came from the lowest level of the heap, meaning it is one of the smallest elements in the heap, so the sift-down will likely take many steps to move it back down.<ref name=MacKay05>{{cite web
 |title=Heapsort, Quicksort, and Entropy
 |first=David J. C. |last=MacKay |author-link=David J. C. MacKay
 |date=December 2005
 |url=https://inference.org.uk/mackay/sorting/sorting.html
 |access-date=2021-02-12
}}</ref> In top-down heapsort, each step of {{code|siftDown}} requires two comparisons, to find the minimum of three elements: the new node and its two children.

Bottom-up heapsort conceptually replaces the root with a value of −∞ and sifts it down using only one comparison per level (since no child can possibly be less than −∞) until the leaves are reached, then replaces the −∞ with the correct value and sifts it ''up'' (again, using one comparison per level) until the correct position is found.

This places the root in the same location as top-down {{code|siftDown}}, but fewer comparisons are required to find that location.  For any single {{code|siftDown}} operation, the bottom-up technique is advantageous if the number of downward movements is at least {{frac|2|3}} of the height of the tree (when the number of comparisons is {{frac|4|3}} times the height for both techniques), and it turns out that this is more than true on average, even for worst-case inputs.<ref name="fleischer">{{cite journal |last=Fleischer |first=Rudolf |title=A tight lower bound for the worst case of Bottom-Up-Heapsort |journal=Algorithmica |volume=11 |issue=2 |date=February 1994 |pages=104–115 |doi=10.1007/bf01182770 |url=http://staff.gutech.edu.om/~rudolf/Paper/buh_algorithmica94.pdf |hdl=11858/00-001M-0000-0014-7B02-C|s2cid=21075180 |hdl-access=free }} Also available as {{cite tech report |last=Fleischer |first=Rudolf |title=A tight lower bound for the worst case of Bottom-Up-Heapsort |date=April 1991 |institution=[[Max Planck Institute for Informatics|MPI-INF]] |number=MPI-I-91-104 |url=http://pubman.mpdl.mpg.de/pubman/item/escidoc:1834997:3/component/escidoc:2463941/MPI-I-94-104.pdf}}</ref>

A naïve implementation of this conceptual algorithm would cause some redundant data copying, as the sift-up portion undoes part of the sifting down.  A practical implementation searches downward for a leaf where −∞ ''would'' be placed, then upward for where the root ''should'' be placed.  Finally, the upward traversal continues to the root's starting position, performing no more comparisons but exchanging nodes to complete the necessary rearrangement.  This optimized form performs the same number of exchanges as top-down {{code|siftDown}}.

Because it goes all the way to the bottom and then comes back up, it is called '''heapsort with bounce''' by some authors.<ref>{{cite book |first1=Bernard |last1=Moret |author-link1=Bernard Moret |first2=Henry D. |last2=Shapiro |title=Algorithms from P to NP Volume 1: Design and Efficiency |chapter=8.6 Heapsort |page=528 |publisher=Benjamin/Cummings |year=1991 |isbn=0-8053-8008-6 |quote=For lack of a better name we call this enhanced program 'heapsort with bounce.{{'-}}}}</ref>

 '''function''' leafSearch(a, i, end) '''is'''
     j ← i
     '''while''' iRightChild(j) < end '''do'''
         ''(Determine which of j's two children is the greater)''
         '''if''' a[iRightChild(j)] > a[iLeftChild(j)] '''then'''
             j ← iRightChild(j)
         '''else'''
             j ← iLeftChild(j)
     ''(At the last level, there might be only one child)''
     '''if''' iLeftChild(j) < end '''then'''
         j ← iLeftChild(j)
     '''return''' j

The return value of the <code>leafSearch</code> is used in the modified <code>siftDown</code> routine:<ref name="fleischer"/>

 '''procedure''' siftDown(a, i, end) '''is'''
     j ← leafSearch(a, i, end)
     '''while''' a[i] > a[j] '''do'''
         j ← iParent(j)
     '''while''' j > i '''do'''
         swap(a[i], a[j])
         j ← iParent(j)

Bottom-up heapsort was announced as beating quicksort (with median-of-three pivot selection) on arrays of size ≥16000.{{refn|name=Wegener|{{cite journal |last=Wegener |first=Ingo |author-link=Ingo Wegener |title={{sc|Bottom-Up Heapsort}}, a new variant of {{sc|Heapsort}} beating, on an average, {{sc|Quicksort}} (if {{mvar|n}} is not very small) |journal=Theoretical Computer Science |volume=118 |issue=1 |date=13 September 1993 |pages=81–98 |doi=10.1016/0304-3975(93)90364-y |doi-access=free |url=https://core.ac.uk/download/pdf/82350265.pdf}} Although this is a reprint of work first published in 1990 (at the Mathematical Foundations of Computer Science conference), the technique was published by Carlsson in 1987.<ref name=Carlsson/>}}

A 2008 re-evaluation of this algorithm showed it to be no faster than top-down heapsort for integer keys, presumably because modern [[branch prediction]] nullifies the cost of the predictable comparisons that bottom-up heapsort manages to avoid.<ref name=Melhorn>{{cite book |last1=Mehlhorn |first1=Kurt |author1-link=Kurt Mehlhorn |first2=Peter |last2=Sanders |author2-link=Peter Sanders (computer scientist) |title=Algorithms and Data Structures: The Basic Toolbox |chapter=Priority Queues |publisher=Springer |year=2008 |page=142 |isbn=978-3-540-77977-3 |url=http://people.mpi-inf.mpg.de/~mehlhorn/Toolbox.html |chapter-url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/PriorityQueues.pdf#page=16}}</ref>

A further refinement does a [[binary search]] in the upward search, and sorts in a worst case of {{math|(''n''+1)(log<sub>2</sub>(''n''+1) + log<sub>2</sub> log<sub>2</sub>(''n''+1) + 1.82) + ''O''(log<sub>2</sub>''n'')}} comparisons, approaching [[Comparison sort#Number of comparisons required to sort a list|the information-theoretic lower bound]] of {{math|''n'' log<sub>2</sub>''n'' − 1.4427''n''}} comparisons.<ref name=Carlsson>{{cite journal |first=Scante |last=Carlsson |title=A variant of heapsort with almost optimal number of comparisons |journal=Information Processing Letters |volume=24 |issue=4 |pages=247–250 |date=March 1987 |doi=10.1016/0020-0190(87)90142-6 |s2cid=28135103 |url=https://pdfs.semanticscholar.org/caec/6682ffd13c6367a8c51b566e2420246faca2.pdf |archive-url=https://web.archive.org/web/20161227055904/https://pdfs.semanticscholar.org/caec/6682ffd13c6367a8c51b566e2420246faca2.pdf |url-status=dead |archive-date=2016-12-27 }}</ref>

A variant that uses two extra bits per internal node (''n''−1 bits total for an ''n''-element heap) to cache information about which child is greater (two bits are required to store three cases: left, right, and unknown)<ref name=McDiarmid>{{Cite journal |title=Building heaps fast |last1=McDiarmid |first1=C. J. H. |last2=Reed |first2=B. A. |date=September 1989 |journal=Journal of Algorithms |volume=10 |issue=3 |pages=352–365 |doi=10.1016/0196-6774(89)90033-3 |url=http://cgm.cs.mcgill.ca/~breed/2016COMP610/BUILDINGHEAPSFAST.pdf}}</ref> uses less than {{math|''n'' log<sub>2</sub>''n'' + 1.1''n''}} compares.<ref>{{cite journal |title=The worst-case complexity of McDiarmid and Reed's variant of {{sc|Bottom-Up Heapsort}} is less than ''n''&nbsp;log&nbsp;''n'' + 1.1''n'' |first=Ingo |last=Wegener |author-link=Ingo Wegener |journal=Information and Computation |volume=97 |issue=1 |pages=86–96 |date=March 1992 |doi=10.1016/0890-5401(92)90005-Z |doi-access=free}}</ref>