'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 ;
'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'