Soluzione iterativa in tempo lineare:
function HEAP-VERIFY(A : array [1 .. N] of Integer) : boolean;
var flag : boolean;
i : integer;
begin
flag := true;
i := 1;
while flag and (i <= (N div 2)) do
begin
if ((2*i+1) > N) then flag := (A[i] >= A[2*i])
else flag := (A[i] >= A[2*i]) and (A[i] >= A[2*i+1]);
i := i + 1
end;
HEAP-VERIFY := flag
end
Altra soluzione iterativa in tempo lineare:
function HEAP-VERIFY(A : array [1 .. N] of Integer) : boolean;
var i : integer;
begin
i := 2;
while (i <= N) and (A[i div 2] >= A[i]) do i := i + 1;
HEAP-VERIFY := (i > N)
end
Soluzione ricorsiva in tempo lineare:
function HEAP-VERIFY(A : array [1 .. N] of Integer) : boolean;
function REC-VERIFY(A : array [1 .. N] of Integer; i : integer) : boolean;
begin
if (i > (N div 2)) then REC-VERIFY := true
else if ((2*i+1) > N)
then REC-VERIFY := (A[i] >= A[2*i]) and REC-VERIFY(A, 2*i)
and REC-VERIFY(A, 2*i+1)
else REC-VERIFY := (A[i] >= A[2*i]) and (A[i] >= A[2*i+1])
and REC-VERIFY(A, 2*i) and REC-VERIFY(A, 2*i+1)
end;
begin { HEAP-VERIFY }
HEAP-VERIFY := REC-VERIFY(A, 1)
end { HEAP-VERIFY }