(*  Tietorakenteet ja algoritmit 1999	*)
(*  Esimerkki 4-7 : heapsort 9.9.1999 MM 	*)
program Esim4_7;

import TRA;


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

procedure heapsort(L:LIST); 
var	A:PRIQUEUE;
begin	
	PRIQUEUE_CREATE(A, LIST_TYPE(L));
	while (LIST_FIRST(L)<>LIST_EOL(L)) do
		begin
		 PRIQUEUE_INSERT(A, LIST_RETRIEVE(L, LIST_FIRST(L)),
		    FLOAT_LIST_RETRIEVE(L, LIST_FIRST(L)));
		 LIST_DELETE(L, LIST_FIRST(L));
		end;
	while (not PRIQUEUE_EMPTY(A)) do
		begin
		 LIST_INSERT(L, LIST_EOL(L), PRIQUEUE_MIN(A));
		 PRIQUEUE_DELETEMIN(A);
		end;
end;

var	L:LIST;
begin
	FLOAT_LIST_CREATE(L);
	LIST_CONSTRUCT_RANDOM(L, 10, 1, 10);
	LIST_PRINT(L);writeln;
	heapsort(L);
	LIST_PRINT(L);writeln;
end.