For the next question, we look again at priority queues. A priority queue is a queue...

Transcribed Image Text:

For the next question, we look again at priority queues. A priority queue is a queue in which each element has a priority, and where dequeueing always returns the item with the greatest priority in the queue We start by defining a class of priority queue elements (PQ-elements for short): class PQElement: def _init_(self, v, p): self.val = v self.priority p So, a PQ-element is a pair consisting of a value (which can be anything, e.g. an integer, a string, an array, etc.) and a priority (which is an integer). In Lab 5 we also implemented the_str_ function to be able to print PQ-elements. Question 7 Write a Python class PQueue that implements a priority queue using a heap of PQElement 's. In particular, you need o implement 5 functions: one for creating an empty priority queue • one for returning the size of the priority queue • one for enqueueing a new PQ-element in the priority queue • one for dequeueing from the priority queue the PQ-element with the greatest priority • one that prints the elements of the priority queue into a string (call this one _str_) Test each of the functions on examples of your own making. For example, running: pq = PQueue () A = [(1,9), (3,7), (13,-3), (0, 10), (4,6), (5,5), (6,4), (2,8), (7,3), (9, 1), (14,-4), (10, 0), (11,-1), (8,2), (12,-2)] for x in A: pq.enq (PQElement(x [0],x[1])) print (pq) print (pq.deq(),pq) should give this printout: [(0,10), (1,9), (2,8), (3,7), (4,6), (5,5), (6,4),(7,3), (8,2), (9, 1), (10,0), (11,-1), (12,-2), (13,-3), (14,-4)] (0,10) [(1,9), (2,8), (3,7),(4,6), (5,5), (6,4), (7,3), (8,2), (9, 1), (10,0), (11,-1), (12,-2), (13,-3), (14,-4) 1. Note: the print function should print the queue elements in descending priority order, without changing the queue. One idea is to use the function toSorted Array from Question 4. Activate Wi Go to Settings t For the next question, we look again at priority queues. A priority queue is a queue in which each element has a priority, and where dequeueing always returns the item with the greatest priority in the queue We start by defining a class of priority queue elements (PQ-elements for short): class PQElement: def _init_(self, v, p): self.val = v self.priority p So, a PQ-element is a pair consisting of a value (which can be anything, e.g. an integer, a string, an array, etc.) and a priority (which is an integer). In Lab 5 we also implemented the_str_ function to be able to print PQ-elements. Question 7 Write a Python class PQueue that implements a priority queue using a heap of PQElement 's. In particular, you need o implement 5 functions: one for creating an empty priority queue • one for returning the size of the priority queue • one for enqueueing a new PQ-element in the priority queue • one for dequeueing from the priority queue the PQ-element with the greatest priority • one that prints the elements of the priority queue into a string (call this one _str_) Test each of the functions on examples of your own making. For example, running: pq = PQueue () A = [(1,9), (3,7), (13,-3), (0, 10), (4,6), (5,5), (6,4), (2,8), (7,3), (9, 1), (14,-4), (10, 0), (11,-1), (8,2), (12,-2)] for x in A: pq.enq (PQElement(x [0],x[1])) print (pq) print (pq.deq(),pq) should give this printout: [(0,10), (1,9), (2,8), (3,7), (4,6), (5,5), (6,4),(7,3), (8,2), (9, 1), (10,0), (11,-1), (12,-2), (13,-3), (14,-4)] (0,10) [(1,9), (2,8), (3,7),(4,6), (5,5), (6,4), (7,3), (8,2), (9, 1), (10,0), (11,-1), (12,-2), (13,-3), (14,-4) 1. Note: the print function should print the queue elements in descending priority order, without changing the queue. One idea is to use the function toSorted Array from Question 4. Activate Wi Go to Settings t

Answer rating: 100% (QA)

an implementation of a priority queue PQueue using a heap of PQElement s in Python class PQElement def initself v p selfval v selfpriority p def strse... View the full answer