heap-sort as we have previously observedrealizing priority queue with heap has the advantage that all the methods in the priority queue adt run in logarithmic time or better hencethis realization is suitable for applications where fast running times are sought for all the priority queue methods thereforelet us again consider the pq sort schemethis time using heap-based implementation of the priority queue during phase the ith add operation takes (log itimesince the heap has entries after the operation is performed therefore this phase takes ( log ntime (it could be improved to (nwith the bottom-up heap construction described in section during the second phase of pq sortthe jth remove min operation runs in (log( ))since the heap has entries at the time the operation is performed summing over all jthis phase takes ( log ntimeso the entire priority-queue sorting algorithm runs in ( log ntime when we use heap to implement the priority queue this sorting algorithm is better known as heap-sortand its performance is summarized in the following proposition proposition the heap-sort algorithm sorts collection of elements in ( log ntimeassuming two elements of can be compared in ( time let us stress that the ( log nrunning time of heap-sort is considerably better than the ( running time of selection-sort and insertion-sort (section implementing heap-sort in-place if the collection to be sorted is implemented by means of an array-based sequencemost notably as python listwe can speed up heap-sort and reduce its space requirement by constant factor using portion of the list itself to store the heapthus avoiding the use of an auxiliary heap data structure this is accomplished by modifying the algorithm as follows we redefine the heap operations to be maximum-oriented heapwith each position' key being at least as large as its children this can be done by recoding the algorithmor by adjusting the notion of keys to be negatively oriented at any time during the execution of the algorithmwe use the left portion of cup to certain index to store the entries of the heapand the right portion of cfrom index to to store the elements of the sequence thusthe first elements of (at indices provide the array-list representation of the heap in the first phase of the algorithmwe start with an empty heap and move the boundary between the heap and the sequence from left to rightone step at time in step ifor nwe expand the heap by adding the element at index