#!/usr/bin/python
#Copyleft (C) 1996 William Totten
#biell@pobox.com

#This library implements a heap data structure and its methods
#A Python list is used to simulate an array. This implimentation will
#  have dynamic size because this is so easily done in this language.
#The version of heap sort provided below writes the elements to a new list,
#  then returns it.

class heap:
	def __init__(s, type):
		s.data=[0]
		if(type=='max'):
			s.type=1	
		elif(type=='min'):
			s.type=0
		else:
			raise AttributeError, type

	def make_empty(s):
		s.data=[0]

	def is_empty(s):
		return s.data[0]==0
	
	def size(s):
		return s.data[0]

	def insert(s, elt):
		s.data.append(None)
		i=s.data[0]=s.data[0]+1

		while(i>1 and not s._compare(int(i/2), elt)):
			s.data[i]=s.data[int(i/2)]
			i=i/2
		s.data[i]=elt

	def delete(s):
		if(s.is_empty()):
			return None
		min=s.data[1]
		s.data[1]=s.data[-1]
		del s.data[-1]; s.data[0]=s.data[0]-1
		i=1; j=2	#j will always be i*2 or i*2+1

		while(j<s.data[0]):
			if(not s._compare(j, s.data[j+1])):
				j=j+1
			if(not s._compare(i, s.data[j])):
				s._swap(i, j)
				i=j
				j=j*2
			else:
				break
		else:
			if(s.data[0]==j and not s._compare(i, j)):
				s._swap(i, j)	
		return min

	def _compare(s, i, j):
		if(s.type):
			return s.data[i]>j
		else:
			return s.data[i]<j

	def _swap(s, i, j):
		tmp=s.data[i]
		s.data[i]=s.data[j]
		s.data[j]=tmp

	def __str__(s):
		return str(s.data[1:])

def heap_sort(list):
	h=heap('min')
	sorted_list=[]

	for i in list:
		h.insert(i)
	while(h.size()<>0):
		sorted_list.append(h.delete())

	return sorted_list

if __name__ == '__main__':
	from posix import times
	list=[23,90,34,56,78,11,1,9,87,142,984,128,842,724,83,29,88,66,9]
	print list
	t=times()[0]
	print heap_sort(list), "\nUser Time: ", times()[0] - t