Thread: heap sort

A heap is a structure where items are stored in an array in such a way so that each item is guaranteed to be larger than the items at two other specific locations. Each of those items are also larger than two more, and so on. It's a binary structure compressed into a linear array:

Code:

         X
      /     \
    T         O
   / \       / \
  G   S     M   N
 /\   /\   /
A  E R  A I

1 2 3 4 5 6 7 8 9 10 11 12
X T O G S M N A E R  A  I

The heapsort is a method of building a heap and then removing the largest element repeatedly until the data is sorted. Here's the basic idea:

Code:

#include <stdio.h>

#define less(a, b) ((a) < (b))

static void exchange ( int *a, int *b )
{
  int t = *a;
  *a = *b;
  *b = t;
}

static void fixDown ( int *a, int k, int N )
{
  int j;
  while ( 2 * k <= N ) {
    j = 2 * k;
    if ( j < N && less ( a[j], a[j+1] ) )
      j++;
    if ( !less ( a[k], a[j] ) )
      break;
    exchange ( &a[k], &a[j] );
    k = j;
  }
}

static void heapsort ( int *a, int l, int r )
{
  int k, N = r - l + 1;
  int *pq = a + l - 1;
  for ( k = N / 2; k >= 1; k-- )
    fixDown ( pq, k, N );
  while ( N > 1 ) {
    exchange ( &pq[1], &pq[N] );
    fixDown ( pq, 1, --N );
  }
}

int main ( void )
{
  int i;
  int a[10] = {8,3,9,1,0,5,9,3,6,4};
  heapsort ( a, 0, 9 );
  for ( i = 0; i < 10; i++ )
    printf ( "%d ", a[i] );
  printf ( "\n" );
  return 0;
}

-Prelude