comment  This example doesn't work with marst 2.1 because of incorrect
         passing a formal parameter called by name to other procedure (but
         it does work with marst 2.2). This example program was reported by
         Paulo Barreto 
        ALGORITHM 232
        J. W. J. Williams (Received 1 Oct. 1963 and revised 15 Feb. 1964)
        Elliott Bros. (London) Ltd., Borehamwood, Herts, England
    comment  The following procedures are related to TREESORT
          [R. W. Floyd, Alg. 113, Comm. ACM 5 (Aug. 1962), 434, and
          A. F. Kaupe, Jr., Alg. 143 and and 144, Comm. ACM 5 (Dec. 1962),
          604] but avoid the use of pointers and so preserve storage space.
          All the procedures operate on single word items, stored as
          elements 1 to n of the array A. The elements are normally so
          arranged that A[i] <= A[j] for 2 <= j <= n, i = j % 2. Such an
          arrangement will be called a heap. A[1] is always the least
          element of the heap.
            The procedure SETHEAP arranges n elements as a heap, INHEAP
          adds a new element to an existing heap, OUTHEAP extracts the
          least element from a heap, and SWOPHEAP is effectively the
          result of INHEAP followed by OUTHEAP. In all cases the array A
          contains elements arranged as a heap on exit.
            SWOPHEAP is essentially the same as the tournament sort
          described by K. E. Iverson - A Programming Language, 1962,
          pp. 223--226 - which is a top to bottom method, but it uses an
          improved storage allocation and initialisation. INHEAP resembles
          TREESORT in being a bottom to top method. HEAPSORT can thus be
          considered as a marriage of these two methods.
            The procedures may be used for replacement-selection
          sorting, for sorting the elements of an array, or for choosing
          the current minimum of any set of items to which new items are
          added from time to time. The procedures are the more useful
          because the active elements of the array are maintained densely
          packed, as elements A[1] to A[n]
    procedure SWOPHEAP(A, N, IN, OUT); 
      value IN, N;
      integer N;
      real IN, OUT;
      real array A;
    comment  SWOPHEAP is given an array A, elements A[1] to A[n]
            forming a heap, n >= 0. SWOPHEAP effectively adds the element in
            to the heap, extracts ans assigns to out the value of the least
            member of the resulting set, and leaves the remaining elements
            in a heap of the original size. In this process elements 1 to
            (n + 1) of the array A may be disturbed. The maximum number of
            repetitions of the cycle labeled scan is log_2 n;
        integer I, J;
        real TEMP, TEMP1;
        if IN NOTLESS A[1] then OUT := 1 else begin;
            I := 1;
            A[N + 1] := IN;
            comment  this last statement is only
                    necessary in case j = n at some stage, or n = 0
            OUT := A[1];
            SCAN: J := I + I;
            if J NOTLESS N then begin;
                TEMP := A[J];
                TEMP1 := A[J + 1];
                if TEMP1 < TEMP then begin;
                    TEMP := TEMP1;
                    J := J + 1;
                end ;
                if TEMP < IN then begin;
                    A[I] := TEMP;
                    I := J;
                    goto SCAN;
                end ;
            end ;
            A[I] := IN;
        end ;
    end SWOPHEAP;
    procedure INHEAP(A, N, IN); 
      value IN;
      integer N;
      real IN;
      real array A;
    comment  INHEAP is given an array A, elements A[1] to A[n]
            forming a heap and n >= 0. INHEAP adds the element in
            to the heap and adjusts n accordingly. The cycle labeled scan
            may be repeated log_2 n times, but on average is repeated twice
        integer I, J;
        I := N := N + 1;
        SCAN: if I > 1 then begin;
            J := I mod 2;
            if IN < A[J] then begin;
                A[I] := A[J];
                I := J;
                goto SCAN;
            end ;
        end ;
        A[I] := IN;
    end INHEAP;
    procedure OUTHEAP(A, N, OUT);
      integer N;
      real OUT;
      real array A;
    comment  given array A, elements 1 to n of which form a heap,
            n >= 1, OUTHEAP assigns to out the value of A[1], the least
            member of the heap, and rearranges the remaining members as
            elements 1 to n - 1 of A. Also, n is adjusted accordingly;
        SWOPHEAP(A, N - 1, A[N], OUT);
        N := N - 1;
    end OUTHEAP;
    procedure SETHEAP(A, N); 
      value N;
      integer N;
      real array A;
    comment  SETHEAP rearranges the elements A[1] to A[n] to form
          a heap;
        integer J;
        J := 1;
        L: INHEAP(A, J, A[J + 1]);
        if J < N then goto L;
    end SETHEAP;
    procedure HEAPSORTTEST(N); 
      value N;
      integer N;
    comment  HEAPSORT TEST tests the implementation on a random array
          of n elements. This procedure is not part of the original
          algorithm definition, and is only provided for completeness;
        integer I;
        real OUT;
        real array A[1 : N];
        comment  create a test array of n elements
        for I := 1 step 1 until N do
            A[I] := RANDOM;
        end ;
        SETHEAP(A, N);
        comment  CAVEAT - the following loop does not work
        I := N;
        LOOP: OUTHEAP(A, I, OUT);
        A[I + 1] := OUT;
        comment  remember that i is decremented by OUTHEAP
        if I > 1 then goto LOOP;
        comment  HOWEVER, the following code does work
        for I := N step -1 until 2 do
            SWOPHEAP(A, I - 1, A[I], OUT);
            A[I] := OUT;
        end ;
        comment  now check if A is sorted in descending order
        for I := 2 step 1 until N do
            if A[I] > A[I - 1] then begin;
                OUTSTRING(1, "HEAPSORT ERROR!\n");
                goto EXIT;
            end ;
        end ;
        EXIT: ;
    real procedure RANDOM;
    end RANDOM;
    comment  main program
end ;