HEAPSORT.C 

#include <stdlib.h>
#include <stdio.h>


#define uint32 unsigned int

typedef int (*CMPFUN)(int, int);


void ArraySort(int This[], CMPFUN fun_ptr, uint32 the_len)
{
  /* heap sort */

  uint32 half;
  uint32 parent;

  if (the_len <= 1)
    return;

  half = the_len >> 1;
  for (parent = half; parent >= 1; --parent)
  {
    int temp;
    int level = 0;
    uint32 child;

    child = parent;
    /* bottom-up downheap */

    /* leaf-search for largest child path */
    while (child <= half)
    {
      ++level;
      child += child;
      if ((child < the_len) &&
          ((*fun_ptr)(This[child], This[child - 1]) > 0))
        ++child;
    }
    /* bottom-up-search for rotation point */
    temp = This[parent - 1];
    for (;;)
    {
      if (parent == child)
        break;
      if ((*fun_ptr)(temp, This[child - 1]) <= 0)
        break;
      child >>= 1;
      --level;
    }
    /* rotate nodes from parent to rotation point */
    for (;level > 0; --level)
    {
      This[(child >> level) - 1] =
        This[(child >> (level - 1)) - 1];
    }
    This[child - 1] = temp;
  }

  --the_len;
  do
  {
    int temp;
    int level = 0;
    uint32 child;

    /* move max element to back of array */
    temp = This[the_len];
    This[the_len] = This[0];
    This[0] = temp;

    child = parent = 1;
    half = the_len >> 1;

    /* bottom-up downheap */

    /* leaf-search for largest child path */
    while (child <= half)
    {
      ++level;
      child += child;
      if ((child < the_len) &&
          ((*fun_ptr)(This[child], This[child - 1]) > 0))
        ++child;
    }
    /* bottom-up-search for rotation point */
    for (;;)
    {
      if (parent == child)
        break;
      if ((*fun_ptr)(temp, This[child - 1]) <= 0)
        break;
      child >>= 1;
      --level;
    }
    /* rotate nodes from parent to rotation point */
    for (;level > 0; --level)
    {
      This[(child >> level) - 1] =
        This[(child >> (level - 1)) - 1];
    }
    This[child - 1] = temp;
  } while (--the_len >= 1);
}


#define ARRAY_SIZE 250000

int my_array[ARRAY_SIZE];

void fill_array()
{
  int indx;

  for (indx=0; indx < ARRAY_SIZE; ++indx)
  {
    my_array[indx] = rand();
  }
}

int cmpfun(int a, int b)
{
  if (a > b)
    return 1;
  else if (a < b)
    return -1;
  else
    return 0;
}

int main()
{
  int indx;

  fill_array();

  ArraySort(my_array, cmpfun, ARRAY_SIZE);

  for (indx=1; indx < ARRAY_SIZE; ++indx)
  {
    if (my_array[indx - 1] > my_array[indx])
    {
      printf("bad sort\n");
      return(1);
    }
  }

  return(0);
}


HEAPDELETESORT.C

/* Extract the highest priority from the heap */

#define LEFT(k)		(2*k)
#define RIGHT(k)	(2*k+1)
#define EMPTY(c,k)	(k>=c->item_cnt)
#define SWAP(i,j)	{ void *x = c->items[i]; \
			c->items[i] = c->items[j]; \
			c->items[j] = x; }

void MoveDown( collection c, int k )
	{
	int larger, right, left;
	left = LEFT(k);
	right = RIGHT(k);
	if ( !EMPTY(c,k) )	/* Termination condition! */
		{
		larger=left;
		if ( !EMPTY(c,right) )
			{
			if ( ItemCmp( c->items[right], c->items[larger] ) > 0 )
				larger = right;
			}
		if ( ItemCmp( c->items[k], c->items[larger] ) )
			{
			SWAP( k, larger );
			MoveDown( c, larger );
			}
		}
	}

void *HighestPriority( collection c )
/* Return the highest priority item
   Pre-condition: (c is a collection created by a call to
                     ConsCollection) &&
                  (existing item count >= 1) &&
                  (item != NULL)
   Post-condition: item has been deleted from c
*/
	{
	int i, cnt;
	void *save;
	assert( c != NULL );
	assert( c->item_cnt >= 1 );
	/* Save the root */
	save = c->items[0];
	/* Put the last item in the root */
	cnt = c->item_cnt;
	c->items[0] = c->items[cnt-1];
	/* Adjust the count */
	c->item_cnt--;
	/* Move the new root item down if necessary */
	MoveDown( c, 1 );
	return save;
	}