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

class PriorityQueue(object): 'A container Class for a Queue' def __init__(self): 'The Constructor for the Queue' self.q = [] def insert(self, item): 'inserts the number into the queue' self.q.append(item) self.q.sort() def minimum(self): 'returns the smallest number in the queue' return min(self.q) def removeMin(self): 'removes the smallest number from the queue' m = self.minimum() self.q.remove(m) self.q.sort() return m def __len__(self): 'returns the size of the priority queue' return len(self.q) def __getitem__(self, index): 'returns the queue item at that index' return self.q[index] def __str__(self): 'returns a string representing the queue' return str(self.q) def __repr__(self): 'returns the canonical representation of the queue' return repr(self.q) def __iter__(self): 'implements iteration for the queue' return iter(self.q)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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