/*  Tietorakenteet ja algoritmit 1999
    Esimerkki 4-7 : heapsort
    9.9.1999 MM
*/

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

/*
	Ratkaisussa oletetaan, että lista L on liukulukulista,
	ja että PRIORITYTYPE:nä voi käyttää liukulukua.
*/

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)),
		    (float)FLOAT_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);
	}
}

void main() {
	LIST L;
	FLOAT_LIST_CREATE(L);
	LIST_CONSTRUCT_RANDOM(L, 10, 1, 10);
	LIST_PRINT(L);putchar('\n');
	heapsort(L);
	LIST_PRINT(L);putchar('\n');
}