and fast the algorithm should take advantage of the fact that sorting is specialpurpose application in that all of the values to be stored are available at the start this means that we do not necessarily need to insert one value at time into the tree structure heapsort is based on the heap data structure presented in section heapsort has all of the advantages just listed the complete binary tree is balancedits array representation is space efficientand we can load all values into the tree at oncetaking advantage of the efficient buildheap function the asymptotic performance of heapsort is th( log nin the bestaverageand worst cases it is not as fast as quicksort in the average case (by constant factor)but heapsort has special properties that will make it particularly useful when sorting data sets too large to fit in main memoryas discussed in sorting algorithm based on max-heaps is quite straightforward first we use the heap building algorithm of section to convert the array into max-heap order then we repeatedly remove the maximum value from the heaprestoring the heap property each time that we do sountil the heap is empty note that each time we remove the maximum element from the heapit is placed at the end of the array assume the elements are stored in array positions through - after removing the maximum value from the heap and readjustingthe maximum value will now be placed in position of the array the heap is now considered to be of size removing the new maximum (rootvalue places the second largest value in position of the array at the end of the processthe array will be properly sorted from least to greatest this is why heapsort uses max-heap rather than min-heap as might have been expected figure illustrates heapsort the complete java implementation is as followsstatic void heapsort( [ /heapsort maxheap new maxheap(aa lengtha length)for (int = < lengthi++/now sort removemax()/removemax places max at end of heap because building the heap takes th(ntime (see section )and because deletions of the maximum element each take th(log ntimewe see that the entire heapsort operation takes th( log ntime in the worstaverageand best cases while typically slower than quicksort by constant factorheapsort has one special advantage over the other sorts studied so far building the heap is relatively cheaprequiring th(ntime removing the maximum element from the heap requires th(log ntime thusif we wish to find the largest elements in an arraywe can do so in time th( log nif is smallthis is substantial improvement