# pqueue implemented as heap
# items must have the item.value filled 

class container:
	def __init(self):
		pass
class heap:
	def __init__(self):
		self.__items = [None]
		self.__items_len = 0

	def isempty(self):
		return self.__items_len==0;

	def min(self):
		if self.__items_len == 0:
			raise IndexError("pop from an empty heap")
		return self.__items[1];

	def append(self,new):
		# just not to be always checking if reached the first element
		self.__items[0]=new
		self.__items_len +=1
		hole = self.__items_len;
		self.__items.append(None)
		# percolate up
		while new.value < self.__items[hole/2].value:
			self.__items[hole] = self.__items[hole/2]
			hole /=2
		self.__items[hole] = new

	def pop(self):
		if self.__items_len == 0:
			raise IndexError("pop from an empty heap")
		min = self.__items[1]
		self.__items[1] = self.__items[self.__items_len]
		self.__percolate_down(1)
		self.__items_len -=1
		return min

	def importlist(self,elements):
		self.__items = [None]
		self.__items_len = 0
		for element in elements:
			self.__items.append(element)
			self.__items_len +=1
		for i in range(self.__items_len/2,0,-1):
			self.__percolate_down(i)

	def __percolate_down(self,hole):
		tmp = self.__items[hole]
		
		while hole*2 <= self.__items_len:
			child = hole*2
			if (child != self.__items_len and
					 self.__items[child+1].value < self.__items[child].value):
				child+=1
			if self.__items[child].value<tmp.value:
				self.__items[hole] = self.__items[child]
			else:
				break
			hole = child
		
		self.__items[hole]=tmp
	
#values = [10,45,12,9,8,7,4,5,1,2,3]
#keys = ['A','B','C','D','E','F','G','H','I','J','K']

#pq = heap()
#objs=[]
#for k in range(len(keys)):
#	obj = container()
#	obj.value = values[k]
#	obj.key = keys[k]
#	objs.append(obj)
#	pq.append(obj)

#pq.importlist(objs)
#print pq.min().key , pq.pop().value
#print pq.min().key , pq.pop().value