def fixheap(array, heaplen, index, greaterthan): |
def fixheap(array, heaplen, index): |
|
|
if (lc < heaplen and greaterthan(array[lc], array[index]) and (rc >= heaplen or (rc < heaplen and not greaterthan(array[rc], array[lc])))): (array[index], array[lc]) = (array[lc], array[index]) fixheap(array, heaplen, lc, greaterthan) |
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) |
elif (rc < heaplen and greaterthan(array[rc], array[index]) and greaterthan(array[rc], array[lc])): (array[index], array[rc]) = (array[rc], array[index]) fixheap(array, heaplen, rc, greaterthan) |
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, greaterthan): |
def makeheap(array): |
fixheap(array, len(array), i, greaterthan) |
fixheap(array, len(array), i) |
def heapsort(array, cmp=lambda x, y: x > y): makeheap(array, cmp) |
def heapsort(array): makeheap(array) |
fixheap(array, i, 0, cmp) |
fixheap(array, i, 0) |
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) 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)