binary trees heapsort the simplicity and efficiency of the heap structure can be applied to the sorting problem the heapsort algorithm builds heap from sequence of unsorted values and then extracts the items from the heap to create sorted sequence simple implementation consider the function in listing we create max-heap with enough capacity to store all of the values in theseq each value from the sequence is then inserted into the heap after thatthe values are then extracted from the heapone at timeand stored back into the original sequence structure in reverse order since we are using max-heapeach time value is extractedwe get the next largest value in sorted order the heapsort algorithm is very efficient and only requires ( log ntime in the worst case the construction of the heap requires ( log ntime since there are items in the sequence and each call to add(requires log time extracting the values from the heap and storing them into the sequence structure also requires ( log ntime listing simple implementation of the heapsort algorithm def simpleheapsorttheseq )create an array-based max-heap len(theseqheap maxheapn build max-heap from the list of values for item in theseq heap additem extract each value from the heap and store them back into the list for in rangen - theseq[iheap extract(sorting in place the implementation of the heapsort algorithm provided in listing has one drawbackit requires the use of additional storage to build the heap structure but we don' actually need second array the entire process of building the heap and extracting the values can be done in place--that iswithin the same sequence in which the original values are supplied suppose we are given the array of values shown at the bottom of figure (aand want to sort them using the heapsort algorithm the first step is to construct heap from this sequence of values as you will seewe can do this within the same array without the need for additional storage rememberthe nodes in the heap occupy the elements of the array from front to back we can keep the heap items at the front of the array and those values that have yet to be added to the