I'm coding a O(n) algorithm of 'heapifying' a list in Python. I can't understand why it's not working.
def func(l):
size=len(l)
for root in range((size//2)-1,-1,-1):
child = 2*root+1 #parent of child is target
while(child<size):
#l[child] should be smaller sibling
if child<size-1 and l[child]>l[child+1]:
child+=1
#can we put l[root] in l[child//2]?
if l[root]<=l[child]:
break #yes
#no
l[child//2]=l[child]#move child up
child=2*child+1#move down a level
l[child//2]=l[root]
return l
There are two issues with your function.
The first is quite simple to grasp. You're using the wrong calculation to find the parent of your child index. Rather than child // 2, you should be using (child - 1) // 2. This was causing you to shift some values into the wrong spots.
The second issue is a bit more subtle. If l[root] is larger than one of its children, you're currently overwriting it with that child, and so when you try to insert it in another place later in the list, the original value is no longer available. Probably you should save l[root] at the top of the for loop, then use the saved value any time you're currently examining l[root] later in the code (the if inside the while loop and the final assignment after it ends.
Here's a fixed version of the code, with comments to point out the changes I made:
def func(l):
size=len(l)
for root in range((size//2)-1,-1,-1):
root_val = l[root] # save root value
child = 2*root+1
while(child<size):
if child<size-1 and l[child]>l[child+1]:
child+=1
if root_val<=l[child]: # compare against saved root value
break
l[(child-1)//2]=l[child] # find child's parent's index correctly
child=2*child+1
l[(child-1)//2]=root_val # here too, and assign saved root value
return l