asymptotic analysis of bottom-up heap construction bottom-up heap construction is asymptotically faster than incrementally inserting keys into an initially empty heap intuitivelywe are performing single downheap operation at each position in the treerather than single up-heap operation from each since more nodes are closer to the bottom of tree than the topthe sum of the downward paths is linearas shown in the following proposition proposition bottom-up construction of heap with entries takes (ntimeassuming two keys can be compared in ( time justificationthe primary cost of the construction is due to the down-heap steps performed at each nonleaf position let pv denote the path of from nonleaf node to its "inorder successorleafthat isthe path that starts at vgoes to the right child of vand then goes down leftward until it reaches leaf althoughpv is not necessarily the path followed by the down-heap bubbling step from vthe length pv (its number of edgesis proportional to the height of the subtree rooted at vand thus bound on the complexity of the down-heap operation at we can bound the total running time of the bottom-up heap construction algorithm based on the sum of the sizes of pathsv pv for intuitionfigure illustrates the justification "visually,marking each edge with the label of the nonleaf node whose path pv contains that edge we claim that the paths pv for all nonleaf are edge-disjointand thus the sum of the path lengths is bounded by the number of total edges in the treehence (nto show thiswe consider what we term "right-leaningand "left-leaningedges ( those going from parent to rightrespectively leftchilda particular rightleaning edge can only be part of the path pv for node that is the parent in the relationship represented by left-leaning edges can be partitioned by considering the leaf that is reached if continuing down leftward until reaching leaf each nonleaf node only uses left-leaning edges in the group leading to that nonleaf node' inorder successor since each nonleaf node must have different inorder successorno two such paths can contain the same left-leaning edge we conclude that the bottom-up construction of heap takes (ntime figure visual justification of the linear running time of bottom-up heap construction each edge is labeled with node for which pv contains (if any