There are many explanations of priority queues on the net, including several YouTube videos. Here's a good one, although there are many others. Try to avoid ones that simply give you code (usually in Java or C++).
Create a class called Pqueue which implements a min-priority queue. In other words, you'll always be removing (popping) the smallest element off the queue. You'll need this class in later program(s).
Implement this queue using a Python list as the underlying data structure.
The class should implement the following methods:
push(data) This will push an element onto the queue.
pop() This will pop the smallest element off the queue or None if the queue is empty.
tolist() This will pop() every element off the queue into a list (in order) that it returns. If the queue was empty, it returns an empty list. Once this function returns, the queue is empty.
You can instantiate the Pqueue using either:
Fred = Pqueue()
or
Fred = Pqueue(cmpfunc)
You may need to provide Pqueue with a function to compare two elements, because the usual Python comparison operators (e.g. "<", ">=", etc.) may not be appropriate for the data you're storing in the queue. For instance, suppose you want to store lists as elements in the queue, and to compare one list to another by their lengths -- so that you'll always be popping the shortest list you've previously stored off the queue. In that case you'll have to provide Pqueue with a comparison function that will tell it when one list is smaller than another.
A valid comparison function takes 2 arguments and returns -1 if the first is smaller than the second, 0 if they're equal, and 1 if the second is larger.
So, for your Pqueue with lists as elements, you can code the comparison function below:
def my_cmp(a,b):
if len(a) < len(b): return -1
if len(a) == len(b): return 0
return 1
...and then use your Pqueue this way:
Fred = Pqueue(my_cmp)
Fred.push([2,"hello",[4,3]])
Fred.push([98.33])
Fred.push(["Why not?","...because"])
print (Fred.pop())
[98.33]
print (Fred.pop())
["Why not?, "...because"]
print (Fred.pop())
[2, "hello", [4, 3]]
print (Fred.pop())
None
Inside the definition of Pqueue, you can handle the initialization this way -- defining OrdinaryComparison() function first, and then referring to it in the __init__() method underneath.
class Pqueue:
def OrdinaryComparison(a,b):
if a < b: return -1
if a == b: return 0
return 1
def __init__(self, comparator =
OrdinaryComparison):
self.cmpfunc = comparator
...and thereafter, inside Pqueue, use self.cmpfunc() as the function that compares two elements, because it will be set either to the user's comparison function (e.g. cmpfunc() above) or to the ordinary Python comparison function (OrdinaryComparison()).
Below your main cell(s) in your Notebook, create a cell for testing your queue. Include operations that exercise all of the methods above and print out results.