History of Heapsort

	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): makeheap(array)

Changed: 50,51c49

fixheap(array, i, 0, cmp)

fixheap(array, i, 0)