Heapsort

Heapsort is an optimization of selection sort, a sort algorithm. In general, a selection sort works as follows:

• remove the lowest datum one at a time until the set of data is empty

The naive algorithm for finding the lowest datum, iterating through the list of unsorted data, has O(N²) performance. Heapsort optimizes the algorithm by using a heap data structure to speed finding and removing the lowest datum. It works as follows:

• make a heap of the data (O(N))
• remove items from the heap one at a time until the heap is empty (O(N lg N))

It can be performed in place with constant auxiliary storage; the "fixheap" routine given below uses tail recursion, and a good compiler or interpreter (such as any Scheme implementation) or a competent programmer can straightforwardly convert the algorithm to an iterative form. No other O(N lg N) sort can be performed with constant auxiliary storage.

Here's an implementation in the Python programming language:

def reverserange(n):
    list = range(n)
    list.reverse()
    return list

def fixheap(array, heaplen, index):
    lc = 2 * index + 1  # left child
    rc = lc + 1         # right child

    # if the left child is inside the heap and the max of the 3, move it up:
    if (lc < heaplen and array[lc] > array[index] and
            (rc >= heaplen or
            (rc < heaplen and array[rc] <= array[lc]))):
        array[index], array[lc] = array[lc], array[index]
        fixheap(array, heaplen, lc)

    # else if the right child is, move it up:
    elif (rc < heaplen and array[rc] > array[index] and array[rc] > array[lc]):
        array[index], array[rc] = array[rc], array[index]
        fixheap(array, heaplen, rc)

def makeheap(array):
    for i in reverserange(len(array)/2):
        fixheap(array, len(array), i)

def heapsort(array):
    makeheap(array)
    for i in reverserange(len(array)):
        (array[i], array[0]) = (array[0], array[i])
        fixheap(array, i, 0)

Talk