CODEWITHSUNDEEP
data-structuresheapheapsortbinary-heap
Parisa
Parisa

Reputation: 159

How to write the Max Heap code without recursion

I have written the MAX-HEAPIFY(A,i) method from the introduction to algorithms book. Now I want to write it without recursion using while loop. Can you help me please?

Upvotes: 3

Views: 10305

Answers (2)

J Doe
J Doe

Reputation: 21

The solution above works but I think that following code is closer to the recursive version

(* Code TP compatible *)
const maxDim = 1000; 
type TElem = integer;
     TArray = array[1..maxDim]of TElem

procedure heapify(var A:TArray;i,heapsize:integer);
var l,r,largest,save:integer;
    temp:TElem;
(*i - index of node that violates heap property
  l - index of left child of node with index i
  r - index of right child of node with index i
  largest - index of largest element of the triplet (i,l,r) 
  save - auxiliary variable to save the value of i 
  temp - auxiliary variable used for swapping *)   
begin
  repeat
    l:=2*i;
    r:=2*i + 1;
    if(l <= heapsize) and (A[l] > A[i]) then
       largest:=l
    else 
       largest:=i;
    if(r <= heapsize) and (A[r] > A[largest]) then
       largest:=r;
    (*Now we save the value i to check properly the termination
     condition of repeat until loop
     The value of i will be modified soon in the if statement *)
    save:=i;
    if largest <> i then
    begin
      temp:=A[i];
      A[i]:=A[largest];
      A[largest]:=temp;
      i:=largest;
    end;
    until largest = save;
    (*Why i used repeat until istead of while ?
     because body of the called procedure will be executed 
     at least once *)
end;

One more thing, in Wirth's Algorithms + Data Structures = Programs
can be found sift procedure without recursion
but we should introduce boolean variable or break to eliminate goto statement

Upvotes: 0

aurilio
aurilio

Reputation: 112

You can use while loop with condition your i <= HEAPSIZE and using all other same conditions , except when you find the right position just break the loop. Code:-

while ( i < = heapsize) {
 le <- left(i)
 ri <- right(i)
 if (le<=heapsize) and (A[le]>A[i])
  largest <- le
 else
  largest <- i 
 if (ri<=heapsize) and (A[ri]>A[largest])
  largest <- ri
 if (largest != i)
 {
   exchange A[i] <-> A[largest]
   i <- largest
 } 
 else
  break
}

Upvotes: 3

Related Questions