program heap_sort_test_auf_Zeitverhalten;
uses crt,dos;

const  maxN  = 10000;
       Datei = 'c:sorting.int';

var a   : array[1..maxN] of word;
    h   : array[0..maxN] of word;   (* der Heap *)
    L,N,M : integer;                (* Anzahl der eingegeben Zahlen*)



procedure lies_words_von_datei(datei : string);
var dat : file of word;
    i   : word;
begin
 i:=0;
 assign(dat,datei);
 reset(dat);
 if not eof(dat) then
   repeat
    i:=i+1;
    read(dat,a[i]);
   until eof(dat);
 L:=i;
 close(dat);
end;

procedure print_words( ab:integer);
var i : integer;
begin
 for i:=ab to L do  write(a[i],' ');
 writeln;
 writeln('*** ende *** ');
end;


procedure print_sortet_words( ab:integer);
var i : integer;
begin
 for i:=ab to M do  write(H[i], '   ');
 writeln;
 writeln('*** ende *** ');
end;


procedure upheap(k :integer);
var v : word;
begin
 v:=H[k];
 while ( H[k div 2] <= v ) do
   begin
      H[k]:=H[k div 2];
      k:=k div 2;
   end;
 H[k]:=v;
end;


procedure downheap( k:integer);
label 0;
var j : integer;
    v : word;
begin
  v:=H[k];
  while k<=N div 2 do
   begin
     j:=k+k;
     if j<N then if H[j]<H[j+1] then j:=j+1;
     if v>=H[j] then goto 0;
     H[k]:=H[j];
     k:=j;
   end;
0: H[k]:=v;
end;


procedure create_heap;
var i : integer;
begin
 H[0]:=65535;           (* Maximum *)
 for i:=1 to L do
   begin
     H[i]:=a[i];
     upheap(i);
   end;
 M:=L;
end;


procedure heapsort;
var k : integer;
    t : word;
begin
 N:=M;
 repeat
   t:=H[1];  H[1]:=H[N];  H[N]:=t;
   N:=N-1;
   downheap(1);
 until N<=1;
end;



(*************************** Main ***********************)
var hour,minute,s,s1 : word;
begin
 clrscr;
 writeln('        *** Heap-Sort ***  : Test des Zeitverhaltens beim  ');
 writeln('                             Sortieren von ',maxN,' Zahlen ');
 writeln('                             aus :  ',Datei,' .' );
 writeln;writeln;
 writeln('Es erfolgt das Einlesen der Zahlen .');
 lies_words_von_datei(Datei);
 clrscr;
 writeln('Fertig ! Jetzt erfolgt das Sortieren . ');
 gettime(hour,minute,s,s1);
 writeln(hour, ':' ,minute, ':' ,s, '.' ,s1 );
 writeln;writeln;

 create_heap;
 writeln('Jetzt wurde gerade der Heap konstruiert : ');
 gettime(hour,minute,s,s1);
 writeln('Das dauerte bis :  ', hour, ':' ,minute, ':' ,s, '.' ,s1 );
 writeln;writeln;

 heapsort;
 gettime(hour,minute,s,s1);
 writeln(hour, ':' ,minute, ':' ,s, '.' ,s1 );
 writeln;writeln;
 readln;
 print_sortet_words(L-150);
 readln;
end.