max_heapify iterative way to go down the heaps to get the next level nodes

248 Views Asked by At

I am trying to write a iterative control loop instead of recursion because it is more efficient can someone tell me if my code makes sense: Recursive version:

def max_heapify(array, i):

left = 2 * i
right = 2 * i + 1
length = len(array) - 1  # for termination condition check
largest = i

if left <= length and array[i] < array[left]:
  largest = left
if right <= length and array[largest] < array[right]:
  largest = right
if largest != i:
  array[i], array[largest] = array[largest], array[i]
  max_heapify(array, largest) 

Iterative version(I think this is wrong??)

def max_heapify(array, i):

  left = 2 * i
  right = 2 * i + 1
  length = len(array) - 1  # for termination condition check
  largest = i

  if left <= length and array[i] < array[left]:
      largest = left
  if right <= length and array[largest] < array[right]:
      largest = right
  if largest != i:
      array[i], array[largest] = array[largest], array[i]
      i= largest

Can I get suggestions to what is wrong with iterative version

1

There are 1 best solutions below

0
On

Actually I think I figured

def max_heapify(array, i):

left = 2 * i
right = 2 * i + 1
length = len(array) - 1  # for termination condition check
largest = i

if left <= length and array[i] < array[left]:
   largest = left
if right <= length and array[largest] < array[right]:
   largest = right
if largest != i:
   array[i], array[largest] = array[largest], array[i]
   i= largest
else:
 break