/* heapsort.c SJ */

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

/* ELEMENT on int */
float elementtoprio(ELEMENT x)
{
  return ELEMENT_INT(x);
}

void heapsort(LIST L)
{
  PRIQUEUE A;

  PRIQUEUE_CREATE(A, LIST_TYPE(L));
  while (LIST_FIRST(L) != LIST_EOL(L))  {
	  PRIQUEUE_INSERT(A, LIST_RETRIEVE(L, LIST_FIRST(L)), 
					  elementtoprio(LIST_RETRIEVE(L, LIST_FIRST(L))));
	  LIST_DELETE(L, LIST_FIRST(L));
  }
  while (! PRIQUEUE_EMPTY(A))  {
	  LIST_INSERT(L, LIST_EOL(L), PRIQUEUE_MIN(A));
	  PRIQUEUE_DELETEMIN(A);
  }
  PRIQUEUE_FREE(A);
} /* heapsort() */

/* kokeellinen osa */

const N = 30;
const M = 100;

int main()
{
  LIST L;
  int i, s;


  INT_LIST_CREATE(L);

  printf("Listaan : ");
  for (i = 1 ; i <= N; i++)   {
	  s = rand()%M;
	  printf("%d ", s);
	  INT_LIST_INSERT(L, LIST_EOL(L), s);
  }
  printf("\n");

  heapsort(L);

  printf("Lajiteltuna ");
  LIST_PRINT(L);
  printf("\n");

  LIST_FREE(L);

  exit(0);
}