//continue the loop, compare the child node and its child nodes } } } // heap_sort function void heap_sort (int array[], int len) { for (int i = len/2 - 1; i >= 0; i--) //Step 1: build up the max-heap { heapify(array, i, len); } for (int i = len - 1; i >= 0; i--) //Step 4: repeat step 2 and 3 till finished { swap(array[0], array[i]); // Step 2: put the max at the end of the array heapify (array, 0, i-1); // Step 3: remove the max from the tree and heapify again } } int main() { //the array that will be sorted int array[] = {42, 1283, 123, 654, 239847, 45, 97, 85, 763, 90, 770, 616, 328, 1444, 911, 315, 38, 5040, 1}; int array_len = sizeof(array)/sizeof(*array); //length of the array heap_sort (array, array_len); return 0; } Measures of presortedness Measures of presortedness measures the existing order in a given sequence. These measures of presortedness decides the number of data that will be put in to the heap during the sorting process as well as the lower bound of running time. Oscillations (Osc) For sequence , Cross(xi) is defined as the number edges of the line plot of X that are intersected by a horizontal line through the point (i, xi). Mathematically, it is defined as . The oscillation(Osc) of X is just the total number of intersections, defined as . Other measures Besides the original Osc measurement, other known measures include the number of inversions Inv, the number of runs Runs, the number of blocks Block, and the measures Max, Exc and Rem. Most of these different measurements are related for adaptive heap sort. Some measures dominate the others: every Osc-optimal algorithm is Inv optimal and Runs optimal; every Inv-optimal algorithm is Max optimal; and every Block-optimal algorithm is Exc optimal and Rem optimal. Algorithm Adaptive heap sort is a variant of heap sort that seeks optimality (asymptotically optimal) with respect to the lower bound derived with the measure of presortedness by taking advantage of the existing order in the data. In heap sort, for a data , we put all n elements into the heap and then keep extracting the maximum (or minimum) for n times. Since the time of each max-extraction action is the logarithmic in the size of the heap, the total running time of standard heap sort is