Heap sort Test

hsort.c

#include <stdio.h>
#include <stdlib.h>
#define swap(a,b) {(a)+=(b);(b)=(a)-(b);(a)-=(b);}

/* use gcc -std=gnu99 for compile   */
/* if you don't want to use -std=gnu99 option,  */
/* then you can use D = (int *)malloc(n * sizeof(int)) */
/* as line 24 and must add declaration of int *D */

typedef struct HeapTree
{
  int *d;
  int size;
} Heap;

void push_heap(Heap *h, int data);
int delete_maximum(Heap *h);

int main(void)
{
  int tmp,n,i;
  printf("put number of data > ");
  scanf("%d",&n);
  int D[n];
  Heap h;
  h.d = (int *)malloc(n * sizeof(int));
  h.size = 0;

  for(i = 0; i < n; i++)
    {
      scanf(" %d",&D[i]);
      push_heap(&h,D[i]);
    }

  printf("\n\nstart sorting...\n");
  for(i = 0; i < n; i++)
    {
      D[i] = delete_maximum(&h);
    }
  
  for(i = 0; i < 5; i++)
    {
      printf("%d : %d\n",i+1,D[i]);
    }
  for(i = n - 5; i < n; i++)
    {
      printf("%d : %d\n",i+1,D[i]);
    }
  
  free(h.d);
  return 0;
}


void push_heap(Heap *h, int data)
{
  int x = h->size++;
  h->d[x] = data;
  
  while( x > 0 )
    {
      if(h->d[x] > h->d[(x - 1)/2]) swap(h->d[x],h->d[(x - 1)/2]);
      x = (x - 1)/2;
    }
  return;
}

int delete_maximum(Heap *h)
{
  int max, x,ret;
  ret = h->d[0];
  
  h->size--;
  swap(h->d[0],h->d[h->size]);

  x = 0;

  /* Does heap have child? */
  while(h->size-1 >= 2*x+1)
    {
      /* definition of max child part */
      if(h->size-1 == 2 * x + 1)
	{
	  max = 2*x + 1;
	}
      else
	{
	  if(h->d[2*x+1] > h->d[2*x+2])
	    {
	      max = 2*x+1;
	    }
	  else
	    {
	      max = 2*x+2;
	    }
	}
      /* definition of max child part end */
      
      if(h->d[x] < h->d[max])
	{
	  swap(h->d[x],h->d[max]);
	  x = max;
	}
      else
	{
	  break;
	}
    }


  return ret;
}