Binary heap: Difference between revisions

Revision as of 00:34, 26 August 2022

Revision as of 05:03, 28 December 2022

Line 157:

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 |url-status=dead }}</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, siftshift 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>