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 priorityqueuesort sorting scheme from section which uses priority queue to sort sequence with elements during phase the -th insert operation ( < <ntakes ( +logitimesince the heap has entries after the operation is performed likewiseduring phase the jth removemin operation ( <= <nruns in time ( +log( + )since the heap has entries at the time the operation is performed thuseach phase takes (nlogntimeso the entire priority-queue sorting algorithm runs in (nlogntime 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 sequence of elements in (nlogntimeassuming two elements ofs can be compared in ( time let us stress that the (nlognrunning 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 sequence to be sorted is implemented by means of an arraywe can speed up heap-sort and reduce its space requirement by constant factor using portion of the sequence itself to store the heapthus avoiding the use of an external heap data structure this is accomplished by modifying the algorithm as follows we use reverse comparatorwhich corresponds to heap where an entry with the largest key is at the top at any time during the execution of the algorithmwe use the left portion of sup to certain index to store the entries of the heapand the right portion of sfrom index to to store the elements of the sequence thusthe first elements of (at indices , provide the array-list representation of the heap (with modified level numbers starting at instead of )that isthe element at index is greater than or equal to its "childrenat indices and 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 ( )we expand the heap by adding the element at index in the second phase of the algorithmwe start with an empty sequence and move the boundary between the heap and the sequence from right to leftone step at time at step ( )we remove maximum element from the heap and store it at index