PROGRAM HEAPSORT;

CONST
  MAXVALUES = 1000;

TYPE
  TINTARRAY = ARRAY[1..MAXVALUES] OF LONGINT;

VAR
  VALUES: TINTARRAY;
  COUNT: LONGINT;
  CODE: INTEGER;
  ELAPSED: REAL;

{ ---------------------------------------------------------------------------
  READFILE
  Purpose:
    Read non-empty lines from FILESPEC into VALUES and set COUNT.
  Parameters:
    FILESPEC - input file path.
  Returns:
    None; updates VALUES and COUNT.
  Variables used:
    INPUTFILE, LINE - text file and current line; CODE - VAL status.
  --------------------------------------------------------------------------- }
PROCEDURE READFILE(CONST FILESPEC: STRING);
VAR
  INPUTFILE: TEXT;
  LINE: STRING;
BEGIN
  WRITE('READING INPUT FILE...');
  ASSIGN(INPUTFILE, FILESPEC);
  RESET(INPUTFILE);
  COUNT := 0;
  WHILE NOT EOF(INPUTFILE) DO
  BEGIN
    READLN(INPUTFILE, LINE);
    IF LINE <> '' THEN
    BEGIN
      INC(COUNT);
      VAL(LINE, VALUES[COUNT], CODE);
    END;
  END;
  CLOSE(INPUTFILE);
  WRITELN('DONE.');
END;

{ ---------------------------------------------------------------------------
  SAVEFILE
  Purpose:
    Write VALUES[1..COUNT] to FILESPEC, one integer per line.
  Parameters:
    FILESPEC - output file path.
  Returns:
    None.
  Variables used:
    OUTPUTFILE - text output; INDEX - array traversal index.
  --------------------------------------------------------------------------- }
PROCEDURE SAVEFILE(CONST FILESPEC: STRING);
VAR
  OUTPUTFILE: TEXT;
  INDEX: LONGINT;
BEGIN
  WRITE('WRITING OUTPUT FILE...');
  ASSIGN(OUTPUTFILE, FILESPEC);
  REWRITE(OUTPUTFILE);
  FOR INDEX := 1 TO COUNT DO
    WRITELN(OUTPUTFILE, VALUES[INDEX]);
  CLOSE(OUTPUTFILE);
  WRITELN('DONE.');
END;

{ ---------------------------------------------------------------------------
  SIFTDOWN
  Purpose:
    Restore the max-heap property below ROOT within VALUES[1..FINISH].
  Parameters:
    ROOT - 1-based subtree root; FINISH - inclusive heap end.
  Returns:
    None; mutates VALUES.
  Variables used:
    CHILD - selected child index; TEMP - swap storage.
  --------------------------------------------------------------------------- }
PROCEDURE SIFTDOWN(ROOT, FINISH: LONGINT);
VAR
  CHILD, TEMP: LONGINT;
BEGIN
  WHILE (2 * ROOT) <= FINISH DO
  BEGIN
    CHILD := 2 * ROOT;
    IF (CHILD < FINISH) AND (VALUES[CHILD] < VALUES[CHILD+1]) THEN
      INC(CHILD);
    IF (VALUES[ROOT] >= VALUES[CHILD]) THEN EXIT;
    TEMP := VALUES[ROOT];
    VALUES[ROOT] := VALUES[CHILD];
    VALUES[CHILD] := TEMP;
    ROOT := CHILD;
  END;
END;

{ ---------------------------------------------------------------------------
  PERFORMSORT
  Purpose:
    Sort VALUES[1..COUNT] in place and measure elapsed time.
  Parameters:
    None; uses global VALUES and COUNT.
  Returns:
    Elapsed duration in seconds as REAL.
  Variables used:
    START, FINISH - heap bounds; TEMP - swap value; STARTTIME/ENDTIME - ticks.
  --------------------------------------------------------------------------- }
FUNCTION PERFORMSORT: REAL;
VAR
  START, FINISH, TEMP: LONGINT;
  STARTTIME, ENDTIME: LONGINT;
BEGIN
  WRITE('SORTING ELEMENTS...');
  STARTTIME := MEM[$40:$6C];
  FOR START := COUNT DIV 2 DOWNTO 1 DO
    SIFTDOWN(START, COUNT);
  FOR FINISH := COUNT DOWNTO 2 DO
  BEGIN
    TEMP := VALUES[1];
    VALUES[1] := VALUES[FINISH];
    VALUES[FINISH] := TEMP;
    SIFTDOWN(1, FINISH -1);
  END;
  ENDTIME := MEM[$40:$6C];
  WRITELN('DONE.');
  PERFORMSORT := (ENDTIME - STARTTIME) / 10.2;
END;

BEGIN
  WRITELN('***HEAPSORT PASCAL***');
  READFILE('C:/INPUT.TXT');
  ELAPSED := PERFORMSORT;
  SAVEFILE('C:/OUTPUT.TXT');
  WRITELN('***RUN COMPLETE***');
  WRITELN('HEAPSORT TOOK ', ELAPSED:0:6, ' SECONDS.');
END.