bottom-up heap construction if we start with an initially empty heapn successive calls to the add operation will run in ( log ntime in the worst case howeverif all key-value pairs to be stored in the heap are given in advancesuch as during the first phase of the heapsort algorithmthere is an alternative bottom-up construction method that runs in (ntime (heap-sorthoweverstill requires th( log ntime because of the second phase in which we repeatedly remove the remaining element with smallest key in this sectionwe describe the bottom-up heap constructionand provide an implementation that can be used by the constructor of heap-based priority queue for simplicity of expositionwe describe this bottom-up heap construction assuming the number of keysnis an integer such that + that isthe heap is complete binary tree with every level being fullso the heap has height log( viewed nonrecursivelybottom-up heap construction consists of the following log( steps in the first step (see figure )we construct ( )/ elementary heaps storing one entry each in the second step (see figure - )we form ( )/ heapseach storing three entriesby joining pairs of elementary heaps and adding new entry the new entry is placed at the root and may have to be swapped with the entry stored at child to preserve the heap-order property in the third step (see figure - )we form ( )/ heapseach storing entriesby joining pairs of -entry heaps (constructed in the previous stepand adding new entry the new entry is placed initially at the rootbut may have to move down with down-heap bubbling to preserve the heap-order property in the generic ith step < <hwe form ( )/ heapseach storing entriesby joining pairs of heaps storing ( - entries (constructed in the previous stepand adding new entry the new entry is placed initially at the rootbut may have to move down with down-heap bubbling to preserve the heap-order property in the last step (see figure - )we form the final heapstoring all the entriesby joining two heaps storing ( )/ entries (constructed in the previous stepand adding new entry the new entry is placed initially at the rootbut may have to move down with down-heap bubbling to preserve the heap-order property we illustrate bottom-up heap construction in figure for