Heap Tree

Heapify
#!/usr/bin/python
""" A modeule containing Heap class"""

def getList():
    return [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

def getRandomList():
    import random

    random.seed()

    l = []
    for i in range(10):
        l.append(random.choice(range(10)))

    return l

def getLeft(index):
    """Get the index of left child

    Args:
        index (int), index of current node

    Returns:
        int, index of the left child
    """
    return index*2+1

def getRight(index):
    """Get the index of right child

    Args:
        index (int), index of current node

    Returns:
        int, index of the right child
    """
    return index*2+2

def maxHeapify(l, index, n):
    """Max heapify the tree

    Args:
        l (list), a list of objects
        i (int), index of current node
        n (int), index of the last node in the list
    """
    # lg(n)
    left = getLeft(index)
    right = getRight(index)

    largest = index
    if left <= n and l[left] > l[index]:
        largest = left

    if right <= n and l[right] > l[largest]:
        largest = right

    if largest != index:
        l[largest], l[index] = l[index], l[largest]
        maxHeapify(l, largest, n)

def buildMaxHeap(l):
    # nlg(n)
    for i in range(len(l)/2 - 1, -1, -1):
        maxHeapify(l, i, len(l)-1)

def heapSort(l):
    # nlg(n)
    buildMaxHeap(l)
    print(l)

    for i in range(len(l)-1, 0, -1):
        l[0], l[i] = l[i], l[0]
        maxHeapify(l, 0, i-1)

def main():
    l = getList();
    print(l)
    heapSort(l)
    print(l)

    l = getRandomList()
    print(l)
    heapSort(l)
    print(l)

if __name__ == '__main__':
    main()
			
Reference