def heapSort(alist):
    ''' Do an in-place heap sort of alist. ''' 
    buildHeap(alist)
    i = len(alist) - 1
    while i > 0:
        # Swap the max item with the "last" item, thus putting
        # the next largest element in its correct position in alist. 
        alist[0], alist[i] = alist[i], alist[0]
        
        # Percolate the new root item downwards to its correct position
        # in the heap. 
        percDown(alist, 0, i)
        i = i - 1
    
    

def buildHeap(alist):
    ''' Turns alist into a max heap ''' 
    n = len(alist)
    i = n/2 - 1
    
    while i >= 0:
        percDown(alist, i, n)
        i = i - 1

def percDown(heap, i, sz):
    ''' 
    Percolate an item downwards in the heap to its correct position, 
    starting at the i'th item. This function assumes we're building a 
    max heap, and that the heap consists of heap[0:sz]. 
    ''' 

    left = 2*i + 1
    right = 2*i + 2
    max = i
    if left < sz and heap[left] > heap[max]:
        max = left
    if right < sz and heap[right] > heap[max]:
        max = right
    if max != i:
        heap[i], heap[max] = heap[max], heap[i]        
        percDown(heap, max, sz)