HomePage | Recent Changes | Preferences

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

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

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)
    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):
    for i in reverserange(len(array)):
        (array[i], array[0]) = (array[0], array[i])
        fixheap(array, i, 0)


HomePage | Recent Changes | Preferences
This page is read-only | View other revisions
Last edited December 16, 2001 7:10 am by Taw (diff)