Up Heapify

down_heapify.py

# Udacity, CS215, 4.2 Down Heapify
# import random
# L = [random.randrange(90)+10 for i in range(20)]
L = [50, 88, 27, 58, 30, 21, 58, 13, 84, 24, 29, 43, 61, 44 ,65, 74, 76, 30, 82, 43]

#Heap shortcuts
def left(i): return i*2+1
def right(i): return i*2+2
def parent(i): return (i-1)/2
def root(i): return i==0
def leaf(L, i): return right(i) >= len(L) and left(i) >= len(L)
def one_child(L, i): return right(i) == len(L)

# Call this routine if the heap rooted at i satisfies the heap property
# *except* perhaps i to its immediate children
def down_heapify(L, i):
    # If i is a leaf, heap property holds
    if leaf(L, i): return
    # If i has one child...
    if one_child(L, i):
        # check heap property
        if L[i] > L[left(i)]:
            # if it fail, swap, fixing i and its child (a leaf)
            (L[i], L[left(i)]) = (L[left(i)], L[i])
        return
    # if i has two children...
    # check heap property
    if min(L[left(i)], L[right(i)]) >= L[i]: return
    # If it fails, see which child is the smaller
    # and swap i's value into that child
    # Afterwards, recurse into that child, which might violate
    if L[left(i)] < L[right(i)]:
        # Swap into left child
        (L[i], L[left(i)]) = (L[left(i)], L[i])
        down_heapify(L, left(i))
        return
    (L[i], L[right(i)]) = (L[right(i)], L[i])
    down_heapify(L, right(i))
    return

up_heapify.py

# Udacity, CS215, Homework 4.5 Up Heapify
# write up_heapify, an algorithm that checks if
# node i and its parent satisfy the heap
# property, swapping and recursing if they don't
#
# L should be a heap when up_heapify is done
#

def up_heapify(L, i):
    # your code here   
    if  parent(i) >= 0:
         if L[parent(i)] > L[i]:
            L[parent(i)], L[i] = L[i], L[parent(i)]
            up_heapify(L, parent(i))       
    return

def parent(i): 
    return (i-1)/2

def test():
    L = [2, 4, 3, 5, 9, 7, 7]
    L.append(1)
    up_heapify(L, 7)
    #print L
    assert 1 == L[0]
    assert 2 == L[1]

test()