MODULE heap;

IMPORT Out;

VAR
  xs : ARRAY 6 OF INTEGER;

PROCEDURE swap(VAR x, y: INTEGER);
VAR t: INTEGER;
BEGIN
  t := x;  x := y;  y := t
END swap;

PROCEDURE outxs(xs : ARRAY OF INTEGER);
VAR i : INTEGER;
BEGIN
  FOR i := 0 TO LEN(xs) - 1 DO
    Out.Int(xs[i], 1);
    Out.Ln;
  END
END outxs;

PROCEDURE heapify(VAR xs : ARRAY OF INTEGER; n, i : INTEGER);
VAR largest : INTEGER;
    left : INTEGER;
    right : INTEGER;
BEGIN
  largest := i;
  left  := 2 * i + 1;
  right := 2 * i + 2;
  
  IF (left < n)  & (xs[left] > xs[largest])  THEN largest := left  END;
  IF (right < n) & (xs[right] > xs[largest]) THEN largest := right END;
  
  IF largest # i THEN
    swap(xs[i], xs[largest]);
    heapify(xs, n, largest)
  END;
END heapify;

PROCEDURE heapSort(VAR xs : ARRAY OF INTEGER);
VAR i : INTEGER;
BEGIN
  FOR i := LEN(xs) DIV 2 - 1 TO 0 BY -1 DO
    heapify(xs, LEN(xs), i)
  END;
  
  FOR i := LEN(xs) - 1 TO 0 BY -1 DO
    swap(xs[0], xs[i]);
    heapify(xs, i, 0)
  END
END heapSort;

BEGIN
  xs[0] := 1;
  xs[1] := 12;
  xs[2] := 9;
  xs[3] := 5;
  xs[4] := 6;
  xs[5] := 10;

  heapSort(xs);

  outxs(xs);
END heap.