I'm trying to implement heapsort according to the original paper but I don't understand how INHEAP
works.
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₂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;
go to scan
end
end;
A[i] := in
end INHEAP;
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 go to L
end SETHEAP
I think the line i:=n:=n+1;
in INHEAP
means that i
is initialized before n
and begin integer j;
in SETHEAP
is supposed to start a loop from 1 to n.
SETHEAP
calls INHEAP
with the first and second elements of A
as arguments. But then why does INHEAP
add the second element to the heap with A[i] := in
?
The code is written in ALGOL 60. Let me answer your questions/doubts one by one:
I think the line
i:=n:=n+1;
in INHEAP means thati
is initialized beforen
This is just multiple assignment like in C and many C-like languages. Assignment should be considered an operator that can be used in an expression and evaluates to the value being assigned. So it is short for:
n:=n+1;
i:=n;
...in that order.
I think ...
begin integer j;
in SETHEAP is supposed to start a loop from 1 ton
.
Yes, this is a bit obscure, but j
is incremented by INHEAP, because the n
parameter is a reference parameter (not a value parameter like in
), meaning n
becomes an alias for the j
variable in SETHEAP
. And as INHEAP
increments n
with the statement n:=n+1
, the j
of SETHEAP
is incremented. If you know C++, then it is like INHEAP
had declared a parameter int &n
SETHEAP calls INHEAP with the first and second elements of A as arguments.
No, that is a misunderstanding, for two reasons:
INHEAP
procedure is only called with one value at the time, which is the third argument: A[j+1]
. The second argument j
is not an array value, but represents the current size of the heap. The subarray A[1...j]
is assumed to be a valid heap. This is true when the first call is made, because an array of size 1 is always a valid heap. The call of INHEAP
is used to take the next value in the array that is not yet part of the heap and insert it into it, growing the heap.INHEAP
, j
has increased (see above), and A[1...j]
will now have become a valid heap. So the next time INHEAP
is called it will be called with j
equal to 2, and passing A[3]
as third argument, ...etc.why does INHEAP add the second element to the heap with A[i] := in?
INHEAP
must assign in
somewhere in the heap -- that is its role! It must shift some elements in the array to find a right spot for in
(making room for it), to finally assign it there. Be aware that n
is not (necessarily) the size of the whole A
array; it is the size of the subarray that is already a heap. It can be confusing that both INHEAP
and SETHEAP
have a n
variable, but it is not the same variable: for SETHEAP
, n
represents the size of A
, while for INHEAP
it represents the size of the subarray that is assumed to be a valid heap.
INHEAP
does not have to do this assignment for the first element, because there is nothing to check: an array with one element has obviously that element at the only possible position, so there is nothing to move. This is why INHEAP
is first called with the second element as value. And as explained above, INHEAP
is called also for any element after the second position.