[Home]History of Heapsort

HomePage | Recent Changes | Preferences

Revision 12 . . December 16, 2001 7:10 am by Taw [simplified python code]
Revision 11 . . December 12, 2001 1:55 pm by Damian Yerrick [relationship to selection sort; copyedit]
Revision 10 . . November 9, 2001 6:20 am by Stephen Gilbert [No need to remove the /Talk link; just remove the obsolete discussion.]

Difference (from prior major revision) (no other diffs)

Changed: 25c25
def fixheap(array, heaplen, index, greaterthan):
def fixheap(array, heaplen, index):

Changed: 28c28

Changed: 30,34c30,34
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)

Changed: 37,40c37,39
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)

Changed: 42c41
def makeheap(array, greaterthan):
def makeheap(array):

Changed: 44c43
fixheap(array, len(array), i, greaterthan)
fixheap(array, len(array), i)

Changed: 46,47c45,46
def heapsort(array, cmp=lambda x, y: x > y):
makeheap(array, cmp)
def heapsort(array):

Changed: 50,51c49
fixheap(array, i, 0, cmp)

fixheap(array, i, 0)

HomePage | Recent Changes | Preferences