heap_sort.py

def heap_sort(m, sort_by):
	def sift_down(m, start, end):
		"""Repair heap whose root element is at index start
		assuming the heaps rooted at its children are valid"""
		root = start

		while 2*root+1 <= end:
			child = 2*root + 1	# left child
			swap = root

			if sort_by(m[swap], m[child]):
				swap = child	# swap if left child is 'larger'

			if child+1 <= end and sort_by(m[swap], m[child+1]):
				swap = child + 1 # swap if right child is 'larger'
			if swap == root:
				return
			else:
				m[root], m[swap] = m[swap], m[root]
				root = swap

	def heapify(m):
		"""If A is a parent node of B then the key of node A is 
		ordered with respect to the key of node B with the same 
		ordering applying across the heap."""
		start = (len(m) - 2) / 2

		while start >= 0:
			sift_down(m, start, len(m)-1)
			start -= 1

	m = list(m)	# deep copy
	heapify(m)

	end = len(m) - 1
	while end > 0:
		m[0], m[end] = m[end], m[0]
		end -= 1
		sift_down(m, 0, end)

	return m