priority queues (heapsthe selection problem the first problem we will examine is the selection problem from section recall that the input is list of elementswhich can be totally orderedand an integer the selection problem is to find the kth largest element two algorithms were given in but neither is very efficient the first algorithmwhich we shall call algorithm ais to read the elements into an array and sort themreturning the appropriate element assuming simple sorting algorithmthe running time is ( the alternative algorithm bis to read elements into an array and sort them the smallest of these is in the kth position we process the remaining elements one by one as an element arrivesit is compared with the kth element in the array if it is largerthen the kth element is removedand the new element is placed in the correct place among the remaining elements when the algorithm endsthe element in the kth position is the answer the running time is ( * (why?if  / then both algorithms are ( notice that for any kwe can solve the symmetric problem of finding the ( )th smallest elementso  / is really the hardest case for these algorithms this also happens to be the most interesting casesince this value of is known as the median we give two algorithms hereboth of which run in ( log nin the extreme case of  / which is distinct improvement algorithm for simplicitywe assume that we are interested in finding the kth smallest element the algorithm is simple we read the elements into an array we then apply the buildheap algorithm to this array finallywe perform deletemin operations the last element extracted from the heap is our answer it should be clear that by changing the heap-order propertywe could solve the original problem of finding the kth largest element the correctness of the algorithm should be clear the worst-case timing is (nto construct the heapif buildheap is usedand (log nfor each deletemin since there are deleteminswe obtain total running time of ( log nif ( /log )then the running time is dominated by the buildheap operation and is (nfor larger values of kthe running time is ( log nif  / then the running time is ( log nnotice that if we run this program for and record the values as they leave the heapwe will have essentially sorted the input file in ( log ntime in we will refine this idea to obtain fast sorting algorithm known as heapsort algorithm for the second algorithmwe return to the original problem and find the kth largest element we use the idea from algorithm at any point in time we will maintain set of the largest elements after the first elements are readwhen new element is read it is compared with the kth largest elementwhich we denote by sk notice that sk is the smallest element in if the new element is largerthen it replaces sk in will then have new smallest elementwhich may or may not be the newly added element at the end of the inputwe find the smallest element in and return it as the answer this is essentially the same algorithm described in herehoweverwe will use heap to implement the first elements are placed into the heap in total time (kwith call to buildheap the time to process each of the remaining elements is ( )to test