begin

   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 <paulo.barreto@terra.com.br>;

   comment
     ALGORITHM 232
     HEAPSORT
     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;
   begin
      integer I, J;
      real TEMP, TEMP 1;
      if IN ⩽ 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 ⩽ N then begin
            TEMP ≔ A[J];
            TEMP 1 ≔ A[J + 1];
            if TEMP 1 < TEMP then begin
               TEMP ≔ TEMP 1;
               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
        only;
   begin
      integer I, J;
      I ≔ N ≔ N + 1;
      SCAN:
      if I > 1 then begin
         J ≔ I ÷ 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;
   begin
      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;
   begin
      integer J;
      J ≔ 1;
      L:
      INHEAP(A, J, A[J + 1]);
      if J < N then goto L
   end SETHEAP;

   procedure HEAPSORT TEST(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;
   begin
      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 begin
            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 begin
            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 begin
            if A[I] > A[I - 1] then begin
               OUTSTRING(1, “HEAPSORT ERROR!\n”);
               goto EXIT
            end
         end;
      OUTSTRING(1, “HEAPSORT IMPLEMENTATION IS CORRECT!\n”);
      EXIT:
   end HEAPSORT TEST;

   real procedure RANDOM;
   begin
      INLINE(“MY_DSA.RETVAL.U.REAL_VAL = RAND();”)
   end RANDOM;

   comment main program;
   HEAPSORT TEST(10)

end