heap sort

# Heap: a Binary Tree (implemented via an array), either a MaxHeap (largest root) or MinHeap (smallest root)
# Constraint: a[k] <= a[ 2*k+1 ] and a[k] <= a[ 2*k+2 ]   (parent is less than it's children)
# Fast (array based, supports in place sorting) and flexible it can support things like Schedulers,
# finding the min, max, median, or kth element in O(1) time, or in Graph Algorithms
# Heapsort O(n log(n))

class Node( object ):
    def __init__( self , key ):
        self.key = key

class HeapSort( object ):

    def __init__( self ):
        self.heap = []

    def heapify( self, A ):
        self.heap = A
        start = ( len(A) - 2) / 2
        while start >= 0:
            self.sift_down( A, start, len(A) - 1)
            start -= 1

    def sift_down( self, A, start, end ):
        current = start
        while current * 2 + 1 <= end:      # at least one child
            child = current * 2 + 1 # left child
            if child + 1 <= end and A[child] < A[child + 1]:    # right child is largest
                child += 1
            if child <= end and A[current] < A[child]:      # parent compared to largest
                A[current], A[child] = A[child], A[current] # swap so largest is parent
                current = child
            else:
                return


    def insert( self, key ):
        """ add to the end of the heap, then fix to the constraint """
        self.heap.append( key )
        self.heapify( self.heap )

    def pop( self ):
        """ remove the root, then make the last element the new root, then fix the constraint """
        self.heap[0], self.heap[ len( self.heap ) -1 ] =  self.heap[ len( self.heap ) -1 ], self.heap[0]   # swap so max now at the end
        max = self.heap.pop()       # extract the last value and reduce the list size
#   self.sift_down( self.heap, 0, len( self.heap) -1 )
        self.heapify( self.heap )   # enforce the constraint
        return max



if __name__ == '__main__':

    a = [ 20, 14, 17, 8, 6, 9, 4, 1, 15 ]
    heapSort = HeapSort()
    heapSort.heapify( a )
    print heapSort.heap
    print 'sorted: ',
    print heapSort.pop(),
    print heapSort.heap

    while len( heapSort.heap ) > 0:
        print heapSort.pop(),


    print
    b = [ 6, 5, 3, 1, 8, 7, 2, 4 ]
    heapSort.heapify( b )
    print heapSort.heap
    print 'sorted: ',
    while len( heapSort.heap ) > 0:
        print heapSort.pop(),