Task 3: Priority Queue Requires: knowing how to implement a class . understanding inheritance In the greedy scheduling algorithm, you will need to consider the parcels one at a time. While we could use a Python list, it has no efficient way to give us items in order according to our priority (e.g. by volume in non-decreasing order). Instead we will use something called a Priority Queue. Like a list, it is also a kind of container that allows you to add and remove items. However, a priority queue removes items in a very specific order: it always removes the item with the highest "priority". If there is a tie for highest priority, it chooses among the tied items the one that was inserted first. (See the docstrings in class PriorityQueue for examples.) A priority queue can prioritize its entries in different ways. For example, we might want to make a priority queue of strings in which shorter have higher priority. Or we want to make a priority queue of employees in which employees with the least seniority have highest priority. Our PriorityQueue class lets client code define what the priority is to be by passing to the initializer a function that can compare two items. Cool! See section 1.4 of the Lecture Notes for information about the type annotation Callable, which is used in that class. A Priority Queue supports the following actions: determine whether the priority queue is empty insert an item with a given priority remove the item with the highest priority File container.py contains the general Container class, as well as a partially- complete PriorityQueue class. PriorityQueue is a child class of Container. You must complete the add() method according to its docstring. It is just one method, but you will have to read carefully and think clearly to complete it. (Notice that we're using a sorted list to implement this class; in later courses, you'll learn about a much more efficient implementation called heaps.) This module contains the Container and PriorityQueue classes. from typing import Any, List, Callable class Container: "A container that holds Objects, This is an abstract class. Only child classes should be instantiated. def add(self, item: Any) -> None: "Add to this Container. raise NotimplementedError def remove(self) -> Any: "Remove and return a single item from this Container raise NotimplementedError def is_empty(self) -> bool: Return True iff this Container is empty. raise NotimplementedError # Used in the doctest examples for PriorityQueue def_shorter(a: str, b: str) -> bool: Return True if is shorter than . RI return len(a) function that is provided at time of initialization All objects in the container must be of the same type. === Private Attributes === queue: The end of the list represents the front of the queue, that is, the next item to be removed. higher priority: A function that compares two items by their priority. If <_higher_priority>(x, y) is true, then x has higher priority than y and should be removed from the queue before y es Representation Invariants === - all elements of <_queue> are of the same type. the elements of <_queue> are appropriate arguments for the function <_higher priority>. - the elements of <_queue> are in order according to the function <_higher priority> _queue: List(Any) _higher priority: Callable[[Any, Any), bool) def __init__(self, higher priority: Callable[[Any, Any), bool]) -> None: Initialize this to an empty PriorityQueue. For any two elements x and y of the queue, if (x, y) is true, then x has higher priority than y. >>> pq = PriorityQueue(str._) >>> pq.is_empty True self._queue = 0 self._higher_priority = higher_priority def add(self, item: Any) -> None: Add to this Priority Queue, >>> # Define a Priority Queue with priority on shorter strings. >>> # l.e., when we remove, we get the shortest remaining string. >>> pq = Priority Queuel shorter) >>> pq.add('fred") >>> pq.add("arju") >>> pq.add("monalisa') >>> pq.add("hat") >>> # 'arju' and fred have the same priority, but 'arju' is behind >>> # 'fred' in the queue because it was added later. >>> pq._queue ['monalisa', 'arju, "fred', 'hat'] >>> pq.remove() That' >>> pq._queue ['monalisa', 'arju', 'fred"] # TODO: Implement this method! pass def remove(self) -> Any: Remove and return the next item from this PriorityQueue. Precondition: this priority queue is non-empty. >>> # When we hit the tie, the one that was added first will be >>> # removed first. . >>> pq = PriorityQueue ( shorter) >>> pq.add("fred") >>> pq.add("arju') >>> pq.add(" monalisa') >>> pq.add("hat") >>> pq.remove() 'hat >>> pq.remove() 'fred' >>> pq.remove() 'arju' >>> pq.remove() 'monalisa' return self._queue.pop() def is_empty(self) -> bool: "*"Return True iff this PriorityQueue is empty. >>>p = PriorityQueue(str.) >>> pq.is_empty True >>> pq.add("fred") >>> pq.is_empty False HHH return not self_queue if __name__ == '_main__': import python_ta python_ta.check_all(config={ allowed-import-modules': ['doctest', 'python_ta', 'typing'), 'disable': ['E1136'). 'max-attributes': 15, }) import doctest doctest.testmod()