a heap sort write by python

heap_sort.py

# -*- coding: utf-8 -*-

"""
This is the heap sort, the algorithm is dive into two step:
first: bulid the max heap
second: heap sort

By: DjvuLee @2012-12-16
"""

import random


def build_max_heap(data):
    pos = len(data)/2 - 1
	for i in xrange(pos, -1, -1):
		down_shift(data, i, len(data)-1)


def down_shift(data, pos, limit):
	left = (pos + 1) * 2 -1
	right = left + 1
	if left > limit:
		return 
	if right > limit:
		if(data[pos]< data[left]):
			data[pos], data[left] = data[left], data[pos]
		return 

	tmp = max(data[left], data[right])
	if data[pos] < tmp:
		if(data[left]> data[right]):
			data[pos], data[left] = data[left], data[pos]
			down_shift(data, left, limit)
		else:
			data[pos], data[right] = data[right], data[pos]
			down_shift(data, right, limit)


def heap_sort(data):
	build_max_heap(data)
	pos = len(data)-1
	k = 1
	for i in xrange(pos, 0, -1 ):
		data[i], data[0] = data[0], data[i]
		down_shift(data, 0, len(data)-1-k)
		k = k + 1
	

def main():
	result = open('heap_sort_result.txt', 'wb')
	
	for k in xrange(10):
		data = []
		for i in xrange(10):
			data.append(int(random.random()* 100))

		result.write(str(data) + '\n')
		#build_max_heap(data)
		result.write('max_heap' + str(data) + '\n')
		heap_sort(data)
		result.write(str(data) + '\n----------------\n')



if __name__ == '__main__':
	main()