O(n) algorithm of heapify

Question

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

@MicahSmith: Not if the indexes are zero-based, as they are in Python. The children of `root` are `2*root+1` and `2*root+2`. — Blckknght, Apr 16 '14 at 03:01
@Blckknght Sounds good. In my DS course, we learned to put root in index 1 and leave index 0 empty. (To both allow pattern above and use as placeholder during heapify.) — Micah Smith, Apr 17 '14 at 22:30

score 3 · Accepted Answer · answered Apr 16 '14 at 03:36

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

score 1 · Answer 2 · edited Nov 29 '20 at 16:04

Nice explanation above, here is a little revised version:

 # heapify in place
 def heapify(A):
    # write your code here
    for root in xrange(len(A)//2 - 1, -1, -1):
        rootVal = A[root]
        child = 2 * root + 1
        while child < len(A):
            if child+1 < len(A) and A[child] > A[child + 1]:
                child += 1
            if rootVal <= A[child]:
                break
            A[child], A[(child - 1)//2] = A[(child - 1)//2], A[child]
            child = child * 2 + 1

O(n) algorithm of heapify

2 Answers2