How to write the Max Heap code without recursion

Parisa picture Parisa · Oct 10, 2014 · Viewed 7.3k times · Source

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?

Answer

aurilio picture aurilio · Oct 10, 2014

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
}