keys into an initially empty heapas the following proposition shows proposition bottom-up construction of heap with entries takes (ntimeassuming two keys can be compared in ( time justificationwe analyze bottom-up heap construction using "visualap proachwhich is illustrated in figure let be the final heaplet be node of tand let (vdenote the subtree of rooted at in the worst casethe time for forming (vfrom the two recursively formed subtrees rooted at ' children is proportional to the height of (vthe worst case occurs when down-heap bubbling from traverses path from all the way to bottom-most node of (vnow consider the path (vof from node to its inorder successor external nodethat isthe path that starts at vgoes to the right child of vand then goes down leftward until it reaches an external node we say that path (vis associated with node note that (vis not necessarily the path followed by down-heap bubbling when forming (vclearlythe size (number of nodesof (vis equal to the height of (vplus one henceforming (vtakes time proportional to the size of ofp( )in the worst case thusthe total running time of bottom-up heap construction is proportional to the sum of the sizes of the paths associated with the nodes of observe that each node of distinct from the root belongs to exactly two such pathsthe path (vassociated with itself and the path (uassociated with the parent of (see figure alsothe root of belongs only to path (rassociated with itself thereforethe sum of the sizes of the paths associated with the internal nodes of is we conclude that the bottom-up construction of heap takes (ntime