Heap Sort
November 6, 2009
A priority queue is a data structure that permits insertion of a new element and retrieval of its smallest member; we have seen priority queues in two previous exercises. Priority queues permit sorting by inserting elements in random order and retrieving them in sorted order. Heapsort uses the heap data structure to maintain a priority queue. The heap is a tree embedded in an array, with the property that the item at each index i of the array is less than the children at indices 2i and 2i+1.
The key to understanding heapsort is a function we call heapify that gives the sub-array A[i .. n] the heap property if the sub-array A[i+1 .. n] already has the property. Heapify starts at the ith element of the array and swaps each element with its smallest child, repeating the operation at that child, stopping at the end of the array or when the current element is smaller than either of its children. Then heapsort works in two phases; the first phase forms an initial heap by calling heapify on each element of the array from n/2 down to 1, then a second phase extracts the elements in order by repeatedly swapping the first element with the last, re-heaping the sub-array that excludes the last element, and recurring with the smaller sub-array that excludes the last element.
Your task is to write a function that sorts an array using the heapsort algorithm, using the conventions of the prior exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.
Programming Praxis 
here is my implementation in c
static void heapify(int arr[], int left, int right); static void sort(int arr[], int left, int right); static void siftup(int arr[], int left, int right, int key); void heapsort(int arr[], int left, int right) { /* transform input file into a heap */ heapify(arr, (right+1)/2, right+1); /* sort the heap */ sort(arr, left+1, right+1); } static void heapify(int arr[], int left, int right) { int i; /* convert to heap */ for(i = left; i > 0; i--) siftup(arr, i, right, arr[i-1]); } static void sort(int arr[], int left, int right) { int i, key; for(i = right; i > 1; i--) { key = arr[i-1]; arr[i-1] = arr[left-1]; /* move the biggest element to the rightmost position in array */ /* move up the next biggest element to root */ siftup(arr, left, i-1, key); } } static void siftup(int arr[], int left, int right, int key) { int i, j; /* move down the tree */ for(i = left, j = 2*i; j <= right; i = j, j = 2*i) { /* j should point to the largest child */ if(j < right && arr[j-1] < arr[j]) j++; /* if child is smaller or equal to parent, than break out of loop */ if(key >= arr[j-1]) break; /* move up the child element */ arr[i-1] = arr[j-1]; } arr[i-1] = key; }