O(n) algorithm of heapify

algorithm, bottom-up, heap, python

Solution

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

Problem

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 ```

Original source