Due Monday Apr 17 at 9pm. Upload to Desire 2 Learn dropbox for homework 10.
This homework exercise will allow you to explore using a priority queue to manage jobs for a high performance computing center. At this center jobs with the highest projected runtime have high priority. Your task is to modify the file linked below to make it a MAX heap (instead of a MIN heap).
Start here: hw_10_priority_queue.py
Overload the > operator in the ClusterJob class using the load factor for each object.
Complete the unit test to make sure ClusterJob objects are compared correctly. a > b.
delmax function that should return the cluster job with the highest runtime. See the delmin function for example.percUp and percDown accordingly so that they ensure the heap stays in heap order (highest at top).maxChildIndex function to determine the index of the largest child of parent p. See minChildIndex for an example that returns the index of the smallest child of parent p. Remember to call maxChildIndex at the appropriate location of the code.Please test with at least 5 cluster job objects and verify they removed in highest to lowest order! You will want to insert job objects, then delete them (delmax function) to verify that the heap is deleting largest to the smallest items in order.
Rename the source code file containing your version of the program according to syllabus.
# solution hw_10_priority_queue.py cs 345 sp 2017
import unittest
class ClusterJob():
def __init__(self, tag, rtime, lines):
self.tag = tag
self.runtime = rtime # estimated runtime in seconds.
self.code_lines = lines # lines of code.
def __str__(self):
return str(self.load_factor())
def __gt__(self, other_obj):
return self.load_factor() > other_obj.load_factor()
def __lt__(self, other_obj):
return self.load_factor() < other_obj.load_factor()
def load_factor(self):
return self.runtime / float(self.code_lines)
class BinHeapList:
"""
Binary heap as a priority queue using a list.
"""
def __init__(self):
"""Creates a new, empty, binary heap as a list."""
self.heap = [0] # set first position to zero placeholder
def __iter__(self):
"""Custom iterator for the tree. (uses breadth first traversal)"""
for i in self.heap[1:]:
yield i.load_factor()
def insert(self, k):
self.heap.append(k) # add to end of list
self.percUp(self.size()) # move new k up the tree
def getMax(self):
return self.heap[1]
def delMax(self):
retval = self.heap[1] # copy the front item.
self.heap[1] = self.heap[-1] # put last item first
self.heap.pop() # clear last item (list decreases by 1)
self.percDown(1) # move first item down the tree
return retval
def percUp(self, p):
"""Maintains heap order property after insertion."""
parent = self.parent(p)
while parent > 0:
if self.heap[p] > self.heap[parent]:
tmp = self.heap[parent]
self.heap[parent] = self.heap[p]
self.heap[p] = tmp
p = parent
parent = self.parent(p)
def percDown(self, p):
"""Maintains heap order property after deletion of root.
Also note that the while loop processes the entire list
"""
left = self.left(p)
while left <= self.size():
max_child = self.maxChildIndex(p)
if self.heap[p] < self.heap[max_child]: # swap child and parent
tmp = self.heap[p]
self.heap[p] = self.heap[max_child]
self.heap[max_child] = tmp
p = max_child # keep moving down the tree
left = self.left(p)
def maxChildIndex(self, p):
"""Determines index of the larger of left and right values."""
left, right = self.left(p), self.right(p)
if right > self.size(): # right node does not exist
return left
elif self.heap[left] > self.heap[right]:
return left
return right
def buildHeap(self, alist):
i = len(alist) // 2 # start in middle of alist.
self.heap = [0] + alist[:] # initialize the heap list
while (i > 0):
self.percDown(i)
i = i - 1
def size(self):
return len(self.heap)-1
def left(self, p):
return p * 2
def right(self, p):
return p * 2 + 1
def parent(self, p):
return p // 2
class TestClusterJob(unittest.TestCase):
"""Unit tests for ClusterJob"""
def test_cluster_job_compare_lt(self):
a = ClusterJob('a', 5, 10)
b = ClusterJob('b', 10, 100)
self.assertEqual(a < b, False)
def test_cluster_job_compare_gt(self):
# write a test that verifies cluster jobs can be compared as a>b
a = ClusterJob('a', 5, 10)
b = ClusterJob('b', 10, 100)
self.assertEqual(a > b, True)
def test_heap_max(self):
# write a test that verifies that the largest job is returned.
a = ClusterJob('a', 50, 100)
b = ClusterJob('b', 10, 100)
c = ClusterJob('c', 30, 100)
d = ClusterJob('d', 90, 100)
e = ClusterJob('e', 5, 100)
f = ClusterJob('f', 99, 100)
print '\nINSERTION ORDER ==>',
print [i.load_factor() for i in [a, b, c, d, e, f]]
h = BinHeapList()
h.buildHeap([a, b, c, d, e, f])
print '\nHEAP BUILT ==>', [i for i in h]
print '\n'
self.assertEqual(h.delMax().load_factor(), .99)
print '\nHEAP BUILT ==>', [i for i in h]
self.assertEqual(h.delMax().load_factor(), .9)
print '\nHEAP BUILT ==>', [i for i in h]
self.assertEqual(h.delMax().load_factor(), .5)
print '\nHEAP BUILT ==>', [i for i in h]
self.assertEqual(h.delMax().load_factor(), .3)
print '\nHEAP BUILT ==>', [i for i in h]
self.assertEqual(h.delMax().load_factor(), .1)
print '\nHEAP BUILT ==>', [i for i in h]
self.assertEqual(h.delMax().load_factor(), .05)
if __name__ == '__main__':
unittest.main()