class PriorityQueue:

	# maxsize: current maximal size of heap (doubles when necessary)
	# last: index of last item
	# item: list of items indexed from 1 through last


	def __init__(self,maxsize):
		self.maxsize = maxsize
		self.item = (maxsize+1) * [0]
		self.last = 0


	def doublemaxsize(self):
		newmaxsize = 2 * self.maxsize
		newitem = (newmaxsize+1) * [0]
		i = 0
		while i < self.maxsize:
			newitem[i] = self.item[i]
			i = i + 1
		self.item = newitem
		self.maxsize = newmaxsize


	def swap(self,i,j):
		t = self.item[i]
		self.item[i] = self.item[j]
		self.item[j] = t


	def up(self,i):
		p = i/2
		if p > 0:
			if self.item[p] > self.item[i]:
				self.swap(i,p)
				self.up(p)


	def insert(self,e):
		if self.last == self.maxsize:
			self.doublemaxsize()
		self.last = self.last+1
		self.item[self.last] = e
		self.up(self.last)


	def down(self,i):
		c = 2*i
		if c <= self.last:
			if c < self.last:
				if self.item[c+1] < self.item[c]:
					c = c+1
			if self.item[i] > self.item[c]:
				self.swap(i,c)
				self.down(c)

	def minimum(self):
		if self.last == 0:
			raise "Heap is empty!"
		return self.item[1]
		

	def deletemin(self):
		if self.last == 0:
			raise "Heap is empty!"
		e = self.item[1]
		self.last = self.last-1
		if self.last > 0:
			self.item[1] = self.item[self.last+1]
			self.down(1)
		return e


	def empty(self):
		return self.last == 0


	def full(self):
		return self.last == self.maxsize


	def size(self):
		return self.last


	def printqueue(self):
		print "========="
		i = 1
		while i <= self.last:
			print self.item[i]
			i += 1
		print "========="