heap sort (Python recipe) by huang chongdi

ActiveState Code (http://code.activestate.com/recipes/577688/)

def heapify(array, start, end, cmp): # array is almost a heap (except the root)
    root = start
    while root * 2 + 1 < end:
        child = root * 2 + 1
        if child + 1 < end:
            v, k = cmp((array[root], root), (array[child], child), (array[child + 1], child + 1))
        else:
            v, k = cmp((array[root], root), (array[child], child))
        if not k == root:
            array[root], array[k] = array[k], array[root]
            root = k
        else:
            break

def build_heap_max(array):
    length = len(array)
    for i in xrange(length / 2, -1, -1):
        heapify(array, i, length, max)

def heap_sort(array):
    build_heap_max(array)
    size = len(array)
    while size > 0:
        array[0], array[size - 1] = array[size - 1], array[0]
        heapify(array, 0, size - 1, max)
        size -= 1