Creating a Loop Version of HEAPIFY Algorithm

[evinda]

Hi! (Wave)

Given the following algorithm:

HEAPIFY(A,i)
   l=LEFT(i);
   r=RIGHT(i)
   largest=i;
   if (l<=size(A) && A[l]>A[largest])
      largest=l;
   if (r<=size(A) && A[r]>A[largest])
      largest=r;
   if (largest!=i)
      swap(A[i], A[largest])
      HEAPIFY(A,largest)

I want to write an alternative version, that uses a loop, instead of recursion.That's what I have tried:

HEAPIFY(A,i)
   l=LEFT(i);
   r=RIGHT(i)
   largest=i;
   if (l<=size(A) && A[l]>A[largest])
      largest=l;
   if (r<=size(A) && A[r]>A[largest])
      largest=r;
    while (largest!=i)
      swap(A[i], A[largest])
       i=largest;
       l=LEFT(i);
       r=RIGHT(i)
       if (l<=size(A) && A[l]>A[largest])
           largest=l;
       if (r<=size(A) && A[r]>A[largest])
          largest=r;

Could you tell me if it is right? (Thinking)

Also, could you explain me why we recall the function [m] HEAPIFY [/m] only in this case:

 if (largest!=i)
      swap(A[i], A[largest])
      HEAPIFY(A,largest)

 

[Future Bruno]

Thanks!Yes, your alternative version is correct. The reason why we recall the function HEAPIFY only in this case is because it ensures that the heap property is maintained. When the swap occurs, it could potentially disrupt the heap property, so it needs to be re-established by recalling the HEAPIFY function with the new largest index.