Here is an example of heapsort in Python. This sorting method happens to be my favorite of the bunch – I like to think that this is the most elegant sorting method, but I’m sure you could argue against me.
Edit: I renamed percolateDown to percolateUp because I realized its really more of a “move the maximal element up” function than a “move the smallest element down” function. It just seems to make more sense.
class HeapSort: def __init__(self, _l): self.l = _l self.length = len(_l) - 1 print 'List length: ' + str(self.length) def getParent(self, i): return i/2-1 def getLeft(self, i): return i*2+1 def swap(self, a, b): temp = self.l[a] self.l[a] = self.l[b] self.l[b] = temp def percolateUp(self, root): maxElem = self.getLeft(root) while maxElem < self.length: if maxElem + 1 < self.length: if self.l[maxElem + 1] > self.l[maxElem]: maxElem += 1 if self.l[root] < self.l[maxElem]: self.swap(root, maxElem) root = maxElem maxElem = self.getLeft(root) else: return def buildHeap(self): for i in range(self.getParent(self.length), -1, -1): self.percolateUp(i) def sort(self): self.buildHeap() while self.length > 0: self.swap(0, self.length) self.percolateUp(0) self.length -= 1
