time of bottom-up heap con structionwhere the paths associated with the internal nodes have been highlighted with alternating colors for examplethe path associated with the root consists of the nodes storing keys and alsothe path associated with the right child of the root consists of the internal nodes storing keys and to summarizeproposition states that the running time for the first phase of heap-sort can be reduced to be (nunfortunatelythe running time of the second phase of heap-sort cannot be made asymptotically better than (nlogn(that isit will always be ohm(nlognin the worst casewe will not justify this lower bound until however insteadwe conclude this by discussing design pattern that allows us to extend the priority queue adt to have additional functionality adaptable priority queues the methods of the priority queue adt given in section are sufficient for most basic applications of priority queuessuch as sorting howeverthere are situations where additional methods would be usefulas shown in the scenarios belowwhich refer to the standby airline passenger application standby passenger with pessimistic attitude may become tired of waiting and decide to leave ahead of the boarding timerequesting to be removed from the