COMPLETE THE FOLLOWING PROGRAM:

priorityqueue.py:

class PriorityQueue: def __init__(self, entries=None, key=lambda x: x): self._entries = list(entries or []) self.key = key self._heapify()

def insert(self, item): self._entries.append(item) self._upheap(len(self))

def _parent(self, i): return (i - 1) // 2

def _children(self, i): left, right = 2 * i + 1, 2 * i + 2 return range(left, min(len(self), right + 1)) def findtop(self): try: return self._entries[0] except: return None

def removetop(self): L = self._entries if len(L) == 0: return None self._swap(0, len(L) - 1) item = L.pop() self._downheap(0) return item

def _swap(self, a, b): L = self._entries L[a], L[b] = L[b], L[a]

# implement this method def _upheap(self, i): pass # implement this method def _downheap(self, i): pass

def __len__(self): return len(self._entries)

def _heapify(self): for i in range(len(self)): self._downheap(len(self) - i - 1) # implement this method def update(self, other): pass # implement this method def _isheap(self): pass

The Priority Queue ADT A PriorityQueue contains a list of objects with priorities and maintains this list in a heap order. You can think of a heap as a tree that is arranged so that objects with smaller priorities are above objects of larger priorities. So, the object with the minimum priority is at the root or equivalently at index 0 of the list The priority of items in a PriorityQueue is determined through a key function. A key function takes an object and returns a comparable object. For example, in the following code, k is a key function klambda x: 1/x[1] for item in L if k(item) 0.5: print(item) (5, 5, 5) A PriorityQueue has the following ADT init(self, entries-None, key-lambda x: x) - Takes a list of objects and a key function and stores them internally. It also creates a priority queue on the entries using the key function. insert (self, item) Inserts an item into the priority queue _parent (self, i) - Takes the index of an item and returns the index of its parent children (self, i) -Takes the index of an item and returns the indices of its children findtop (self) Returns the root of the priority queue. removetop(self) - Removes the root of the priority queue and returns it. _swap (self, a, b) - Takes two indices and swaps their corresponding items. _upheap(self, i) - Takes an index and shifts the item at that index upward until it finds the right place for that item The Priority Queue ADT A PriorityQueue contains a list of objects with priorities and maintains this list in a heap order. You can think of a heap as a tree that is arranged so that objects with smaller priorities are above objects of larger priorities. So, the object with the minimum priority is at the root or equivalently at index 0 of the list The priority of items in a PriorityQueue is determined through a key function. A key function takes an object and returns a comparable object. For example, in the following code, k is a key function klambda x: 1/x[1] for item in L if k(item) 0.5: print(item) (5, 5, 5) A PriorityQueue has the following ADT init(self, entries-None, key-lambda x: x) - Takes a list of objects and a key function and stores them internally. It also creates a priority queue on the entries using the key function. insert (self, item) Inserts an item into the priority queue _parent (self, i) - Takes the index of an item and returns the index of its parent children (self, i) -Takes the index of an item and returns the indices of its children findtop (self) Returns the root of the priority queue. removetop(self) - Removes the root of the priority queue and returns it. _swap (self, a, b) - Takes two indices and swaps their corresponding items. _upheap(self, i) - Takes an index and shifts the item at that index upward until it finds the right place for that item