bheap.py

class BinaryHeap:
	def __init__(self, N):
		self.priorityList = [0]
		self.loadList = [0]
		self.size = 0
		self.maxSize = N

	def insert(self, priority , value):
		if (self.maxSize - 1) >= self.size:
			self.priorityList.append(priority)
			self.loadList.append(value)
			self.size = self.size + 1
			self.percUp(self.size)
		else:
			print "Yigin Dolu"

	def buildHeap(self, prioritys, values):
		i = len(prioritys)/2
		self.size = len(prioritys)
		if self.maxSize >= self.size:
			self.priorityList = [0] + prioritys[:]
			self.loadList = [0] + values[:]
			while i > 0:
				self.percDown(i)
				i -= 1
		else:
			print "Yigin Maximum Elemana Ulasti"

	def percUp(self, i):
		while i > 1:
			if self.priorityList[i] > self.priorityList[i/2]:
				self.priorityList[i/2], self.priorityList[i] = self.priorityList[i], self.priorityList[i/2]
				self.loadList[i/2], self.loadList[i] = self.loadList[i], self.loadList[i/2]
			i = i/2

	def percDown(self, i):
		while (i*2) <= self.size:
			cocuk = i*2
			mc = self.maxChild(i)
			if self.priorityList[i] < self.priorityList[mc]:
				self.priorityList[i], self.priorityList[mc] = self.priorityList[mc], self.priorityList[i]
				self.loadList[i], self.loadList[mc] = self.loadList[mc], self.loadList[i]
			i = mc

	def maxChild(self, i):
		if i*2 > self.size:
			return -1
		else:
			if i*2+1 > self.size:
				return i*2
			else:
				if self.priorityList[i*2] > self.priorityList[i*2+1]:
					return i*2
				else:
					return i*2+1

	def delMax(self):
		if self.size > 0:
			value = self.loadList[1]
			self.priorityList[1] = self.priorityList[self.size]
			self.loadList[1] = self.loadList[self.size]
			self.size -= 1
			self.percDown(1)
			return value
		else:
			print 'Yigin Bos'

class PriorityQueue(BinaryHeap):
	def __init__(self, N):
		self.priorityList = [0]
		self.loadList = [0]
		self.size = 0
		self.maxSize = N

	def enqueue(self, priority, load):
		if self.maxSize > self.size:
			self.priorityList.append(priority)
			self.loadList.append(load)
			self.size += 1
			self.percUp(self.size)
		else:
			i = 1
			maxPri = max(self.priorityList[1:])
			if priority > maxPri:
				index = self.priorityList.index(maxPri)
				self.priorityList[index] = priority
				self.loadList[index] = load
		self.percUp(self.size-1)

	def dequeu(self):
		if self.size > 0:
			load = self.loadList[1]
			self.priorityList[1] = self.priorityList[self.size]
			self.loadList[1] = self.loadList[self.size]
			self.size -= 1
			self.percDown(1)
			return load
		else:
			print 'Kuyruk Bos'