Heap Sort
November 6, 2009
We begin with a simple version that implements the heapsort algorithm directly:
function swap(A,i,j, t) {
t = A[i]; A[i] = A[j]; A[j] = t }
function heapify(A,left,right, p,c) {
for (p=left; (c=2*p) <= right; p=c) {
if (c<right && A[c] < A[c+1]) c++
if (A[p] < A[c]) swap(A, c, p) } }
function sort(A,n, i) {
for (i=int(n/2); i>=1; i--)
heapify(A, i, n)
for (i=n; i>1; i--) {
swap(A, 1, i)
heapify(A, 1, i-1) } }
By moving the swap inline, we can move the invariant part of the swap out of the inner loop:
function heapify(A,left,right, p,c,t) {
t = A[left]
for (p=left; (c=2*p) <= right; p=c) {
if (c<right && A[c] < A[c+1]) c++
if (t < A[c]) A[p] = A[c]; else break }
A[p] = t }
function sort(A,n, i,t) {
for (i=int(n/2); i>=1; i--)
heapify(A, i, n)
for (i=n; i>1; i--) {
t = A[1]; A[1] = A[i]; A[i] = t
heapify(A, 1, i-1) } }
It has been shown empirically that instead of heapifying from the top it is better to sift the item at the top of the heap all the way to the bottom, then sift it back up to its proper position, eliminating the comparison between a parent and its smallest child on the trip down:
function heapify(A,left,right, p,c,t) {
t = A[left]
for (p=left; (c=2*p) <= right; p=c) {
if (c<right && A[c] < A[c+1]) c++
A[p] = A[c] }
for (c=p; (p=int(c/2)) >= left; c=p) {
if (t > A[p]) A[c] = A[p]; else break }
A[c] = t }
function sort(A,n, i,t) {
for (i=int(n/2); i>=1; i--)
heapify(A, i, n)
for (i=n; i>1; i--) {
t = A[1]; A[1] = A[i]; A[i] = t
heapify(A, 1, i-1) } }
Our final version moves the heapify function inline:
function sort(A,n, l,r,p,c,t) {
if (n > 1) {
l = int(n/2) + 1; r = n
while(1) {
if (l > 1) t = A[--l]
else { t = A[r]; A[r--] = A[1]
if (r == 1) { A[1] = t; return } }
for (p=l; (c=2*p) <= r; p=c) {
if (c < r && A[c] < A[c+1]) c++
A[p] = A[c] }
for (c=p; (p=int(c/2)) >= l; c=p) {
if (A[p] < t) A[c] = A[p]; else break }
A[c] = t } } }
Like quicksort, heapsort runs in time O(n log n). The final heapsort is quite fast, nearly as fast as a well-tuned quicksort and without the annoying possibility of a quadratic worst-case. The code, including the test suite from the prior exercise, is collected at http://programmingpraxis.codepad.org/6HryLp9f, but you can’t run it, because codepad doesn’t provide an Awk interpreter.
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; }