Maxheap in Python

Maxheap in Python Homework Sample

Implement a priority queue using MaxHeap, you need to support the following commands. Insert value, print, is Empty, maximum, and extract Max. The code should run in Python 2.7. For more Python programming assignments contact us for a quote.

Solution:

lab3.py

from sys import argv
from pQueue import pQueue

def main(argv):

inputFile = argv[1]
f = open(str(inputFile), “r”)
return f

if __name__ == “__main__”:

pq = pQueue(100)

f = main(argv)

for x in f:
if x[0:6] == ‘insert’:
_x = x
_x = _x.split(‘ ‘)
pq.insert(int(_x[1]))

elif x[0:7] == ‘maximum’:
print pq.maximum()

elif x[0:5] == ‘print’:
pq.printQueue()

elif x[0:7] == ‘isEmpty’:
pq.isEmpty()

elif x[0:10] == ‘extractMax’:
print pq.extractMax()

else:
continue

MaxHeap.py

class MaxHeap(object):

def __init__(self, size):

self.__maxSize = size
self.__length = 0
self.__heap = [float(‘nan’)]

def getHeap(self):
return self.__heap[1:]

def getMaxSize(self):
return self.__maxSize

def setMaxSize(self, ms):
self.__maxSize = ms

def getLength(self):
return self.__length

def setLength(self, l):
self.__length = l

# Custom methods
def parent(self, index):
return (self.__heap[index//2], index//2) if index > 1 else (None,None)

def left_child(self, index):
try:
return self.__heap[2*index], 2*index
except IndexError:
return None, None

def right_child(self, index):
try:
return self.__heap[2*index+1], 2*index+1
except IndexError:
return None, None

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

def bubble_up(self):
value = self.__heap[-1]
i = len(self.__heap) – 1

while True:
parent_value, parent_i = self.parent(i)
if parent_value is not None and value > parent_value:
self.swap(i, parent_i)
i = parent_i
else:
break

def bubble_down(self):
if self.__length == 0:
return
i = 1
value = self.__heap[1]

while True:
left_value, left_i = self.left_child(i)
right_value, right_i = self.right_child(i)

compare_value = None
compare_i = None
if left_value is not None and right_value is not None:
if left_value >= right_value:
compare_value = left_value
compare_i = left_i
else:
compare_value = right_value
compare_i = right_i
elif left_value is not None:
compare_value = left_value
compare_i = left_i
elif right_value is not None:
compare_value = right_value
compare_i = right_i

if compare_value is not None:
if compare_value > value:
self.swap(compare_i,i)
i = compare_i
else:
break
else:
break

”’ Required Methods ”’
def insert(self, data):
self.__heap.append(data)
self.__length += 1
self.bubble_up()

def maximum(self):
# return the max value in the heap
if self.__length:
return self.__heap[1]
else:
raise Exception(“The heap is empty”)

def extractMax(self):
# remove and return the maximum value in the heap
if not self.__length:
raise Exception(“The heap is empty”)
first_index = 1
last_index = len(self.__heap) – 1
self.swap(first_index,last_index)
max_value = self.__heap.pop()
self.__length -= 1
self.bubble_down()
return max_value

def __heapify(self, node):
for value in node:
self.insert(value)

pQueue.py

from MaxHeap import MaxHeap

class pQueue(object):

def __init__(self, size):
self.__myHeap = MaxHeap(size)

def insert(self, data):
self.__myHeap.insert(data)

def maximum(self):
return self.__myHeap.maximum()

def extractMax(self):
return self.__myHeap.extractMax()

def isEmpty(self):
if self.__myHeap.getLength() == 0:
print ‘Empty’
else:
print ‘Not Empty’

def printQueue(self):
print ‘Current Queue:’,(“,”.join([str(num) for num in self.__myHeap.getHeap()]))