Editing Binary heap (section)

==Building a heap==
Building a heap from an array of {{mvar|n}} input elements can be done by starting with an empty heap, then successively inserting each element. This approach, called Williams' method after the inventor of binary heaps, is easily seen to run in {{math|''O''(''n'' log ''n'')}} time: it performs {{mvar|n}} insertions at {{math|''O''(log ''n'')}} cost each.{{efn|In fact, this procedure can be shown to take {{math|Θ(''n'' log ''n'')}} time [[Best, worst and average case|in the worst case]], meaning that {{math|''n'' log ''n''}} is also an asymptotic lower bound on the complexity.<ref name="clrs">{{Introduction to Algorithms|3}}</ref>{{rp|167}} In the ''average case'' (averaging over all [[permutation]]s of {{mvar|n}} inputs), though, the method takes linear time.<ref name="heapbuildjalg">{{cite journal |title=Average Case Analysis of Heap Building by Repeated Insertion |first1=Ryan |last1=Hayward |first2=Colin |last2=McDiarmid |journal=J. Algorithms |year=1991 |volume=12 |pages=126–153 |url=http://www.stats.ox.ac.uk/__data/assets/pdf_file/0015/4173/heapbuildjalg.pdf |doi=10.1016/0196-6774(91)90027-v |citeseerx=10.1.1.353.7888 |access-date=2016-01-28 |archive-url=https://web.archive.org/web/20160205023201/http://www.stats.ox.ac.uk/__data/assets/pdf_file/0015/4173/heapbuildjalg.pdf |archive-date=2016-02-05 }}</ref>}}

However, Williams' method is suboptimal. A faster method (due to [[Robert W. Floyd|Floyd]]{{r|heapbuildjalg}}) starts by arbitrarily putting the elements on a binary tree, respecting the shape property (the tree could be represented by an array, see below). Then starting from the lowest level and moving upwards, sift the root of each subtree downward as in the deletion algorithm until the heap property is restored. More specifically if all the subtrees starting at some height <math>h</math> have already been "heapified" (the bottommost level corresponding to <math>h=0</math>), the trees at height <math>h+1</math> can be heapified by sending their root down along the path of maximum valued children when building a max-heap, or minimum valued children when building a min-heap. This process takes <math>O(h)</math> operations (swaps) per node. In this method most of the heapification takes place in the lower levels. Since the height of the heap is <math> \lfloor \log n \rfloor</math>, the number of nodes at height <math>h</math> is <math>\le \frac{2^{\lfloor \log n \rfloor}}{2^h} \le \frac{n}{2^h}</math>. Therefore, the cost of heapifying all subtrees is:

:<math>
\begin{align}
\sum_{h=0}^{\lfloor \log n \rfloor} \frac{n}{2^h} O(h) 
& = O\left(n\sum_{h=0}^{\lfloor \log n \rfloor} \frac{h}{2^h}\right) \\
& = O\left(n\sum_{h=0}^{\infty} \frac{h}{2^h}\right) \\
& = O(n)
\end{align}
</math>

This uses the fact that the given infinite [[series (mathematics)|series]] <math display="inline">\sum_{i=0}^\infty i/2^i</math> [[Convergent series|converges]].

The exact value of the above (the worst-case number of comparisons during the heap construction) is known to be equal to:

:<math> 2 n - 2 s_2 (n) - e_2 (n) </math>,<ref>{{citation
 | 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
 | url = http://www.deepdyve.com/lp/ios-press/elementary-yet-precise-worst-case-analysis-of-floyd-s-heap-50NW30HMxU}}.</ref>{{efn|This does not mean that ''sorting'' can be done in linear time since building a heap is only the first step of the [[heapsort]] algorithm.}}
where {{math|''s''<sub>2</sub>(''n'')}} is the [[Hamming weight|sum of all digits of the binary representation]] of {{mvar|n}} and {{math|''e''<sub>2</sub>(''n'')}} is the exponent of {{math|2}} in the prime factorization of {{mvar|n}}.

The average case is more complex to analyze, but it can be shown to asymptotically approach {{math|1.8814&nbsp;''n'' − 2 log<sub>2</sub>''n'' + ''O''(1)}} comparisons.<ref>{{cite journal |title=An Average Case Analysis of Floyd's Algorithm to Construct Heaps |first=Ernst E. |last=Doberkat |journal=Information and Control |volume=6 |issue=2 |pages=114–131 |date=May 1984 |doi=10.1016/S0019-9958(84)80053-4 |url=https://core.ac.uk/download/pdf/82135122.pdf |doi-access=free}}</ref><ref>{{cite tech report
 |title=Elementary Average Case Analysis of Floyd's Algorithm to Construct Heaps
 |first=Tomi |last=Pasanen
 |date=November 1996
 |publisher=Turku Centre for Computer Science
 |id=TUCS Technical Report No. 64
 |isbn=951-650-888-X
 |citeseerx=10.1.1.15.9526
}}  Note that this paper uses Floyd's original terminology "siftup" for what is now called sifting ''down''.</ref>

The '''Build-Max-Heap''' function that follows, converts an array ''A'' which stores a complete
binary tree with ''n'' nodes to a max-heap by repeatedly using '''Max-Heapify''' (down-heapify for a max-heap) in a bottom-up manner.
The array elements indexed by
{{nowrap|''[[floor function|floor]]''(''n''/2) + 1}}, {{nowrap|''floor''(''n''/2) + 2}}, ..., ''n''
are all leaves for the tree (assuming that indices start at 1)—thus each is a one-element heap, and does not need to be down-heapified. '''Build-Max-Heap''' runs
'''Max-Heapify''' on each of the remaining tree nodes.

 '''Build-Max-Heap''' (''A''):
     '''for each''' index ''i'' '''from''' ''floor''(''length''(''A'')/2) '''downto''' 1 '''do:'''
         '''Max-Heapify'''(''A'', ''i'')