In Python, Implement a container class PriorityQueue (that is a subclass of the

Question

In Python,

Implement a container class PriorityQueue (that is a subclass of the object class) supporting nine methods:

__init__ which takes no parameter and initializes the object to an empty queue

insert which takes a number as a parameter and inserts the number into the queue, modifying the queue afterward to insure that the number is placed in the correct position

minimum which takes no parameters and returns the smallest number in the queue

removeMin which takes no parameters and removes the smallest number from the queue, returning the value removed

__len__ which takes no parameters and returns the size of the priority queue

__str__ which takes no parameters and returns a string representing the queue

__repr__ which takes no parameters and returns the canonical representation of the queue

__getitem__ which takes an index as a parameter and returns the queue item at that index without modifying the queue

__iter__ which implements iteration for the queue -- iteration should proceed from the smallest to the largest number in the queue

I suggest that you use a list to store the numbers in the priority queue. Your implementation must insure that the list is ordered after every operation (insertion or removal) so that the minimum number is stored in one end of the list. The following shows how the PriorityQueue class and its methods could be used. Note that in my implementation the queue is stored in non-decreasing order (i.e. with the minimum at the front of the queue). You can also write an implementation that stores the queue items in non-increasing order (i.e. with the minimum at the end of the queue). Either implementation is fine, although your choice will impact the way that you write the __getitem__ and __iter__ methods:

Explanation / Answer

pq = [] # list of entries arranged in a heap entry_finder = {} # mapping of tasks to entries REMOVED = '' # placeholder for a removed task counter = itertools.count() # unique sequence count def add_task(task, priority=0): 'Add a new task or update the priority of an existing task' if task in entry_finder: remove_task(task) count = next(counter) entry = [priority, count, task] entry_finder[task] = entry heappush(pq, entry) def remove_task(task): 'Mark an existing task as REMOVED. Raise KeyError if not found.' entry = entry_finder.pop(task) entry[-1] = REMOVED def pop_task(): 'Remove and return the lowest priority task. Raise KeyError if empty.' while pq: priority, count, task = heappop(pq) if task is not REMOVED: del entry_finder[task] return task raise KeyError('pop from an empty priority queue'

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.