python Priority Queue implementation

0
votes

i'm having trouble creating an insert function with the following parameters. The insert function should take in a priority queue, and an element and inserts it using the priority rules -

The priority queue will take a series of tasks and order them based on their importance. Each task has an integer priority from 10 (highest priority) to 1 (lowest priority). If two tasks have the same priority, the order should be based on the order they were inserted into the priority queue (earlier first).

So, as of right now i've created the following code to initialize some of the things needed...

class Tasks():
    __slots__ = ('name', 'priority')

     def __init__(bval):
         bval.name = myName
         bval.priority = myPriority
         return bval

class PriorityQueue():
    __slots__ = ('queue', 'element')

     def __init__(aval):
         aval.queue = queue
         aval.element = element
         return aval

The code i'm trying to write is insert(element, queue): which should insert the elements using the priority queue. Similarly, myPriorty is an integer from 1 to 10.

Similarly can I do the following to insure that I create a priority from 1 to 10...

def __init__(bval , myPriority = 10):
      bval.priority = myPriority
      bval.pq = [[] for priority in range(bval.myPriority)]

so that I can replace myPriority in the insert task with bval.pq

4
pythonpriority-queue
mattgemmell.com/2008/12/08/what-have-you-tried - Tyler Crompton
Style Note: aval and bval should really just be "self". It is also unclear where the variables that you are assigning in the constructors are coming from. - kazagistar
I replaced them with self. @TylerCrompton I've been looking at the heap implementation since i'm now allowed to use the actual priority.queue() call. - user2933041
Using aval and bval confused the heck out of me why I first saw that. Thanks. - Paul Draper

4 Answers

4
votes

Why are you trying to re-invent the wheel?

from Queue import PriorityQueue

http://docs.python.org/2/library/queue.html?highlight=priorityqueue#Queue.PriorityQueue

The lowest valued entries are retrieved first (the lowest valued entry is the one returned by sorted(list(entries))[0]). A typical pattern for entries is a tuple in the form:

(priority_number, data).

I use such a module to communicate between the UI and a background polling thread.

READ_LOOP = 5
LOW_PRI = 3
MED_PRI = 2
HI_PRI = 1
X_HI_PRI = 0

and then something like this:

CoreGUI.TX_queue.put((X_HI_PRI,'STOP',[]))
2
votes

Note that there is a Queue. If you are okay with it being synchronized, I would use that.

Otherwise, you should use a heap to maintain your queue. See Python documentation with an example of that.

0
votes

From a great book "Modern Python Standard Library Cookbook" by Alessandro Molina

Heaps are a perfect match for everything that has priorities, such as a priority queue:

import time
import heapq

class PriorityQueue:
    def __init__(self):
        self._q = []

    def add(self, value, priority=0):
        heapq.heappush(self._q, (priority, time.time(), value))

    def pop(self):
        return heapq.heappop(self._q)[-1]

Example:

>>> def f1(): print('hello')
>>> def f2(): print('world')
>>>
>>> pq = PriorityQueue()
>>> pq.add(f2, priority=1)
>>> pq.add(f1, priority=0)
>>> pq.pop()()
hello
>>> pq.pop()()
world
-2
votes

A deque (from collections import deque) is the python implementation of a single queue. You can add items to one end and remove them from the other. If you have a deque for each priority level, you can add to the priority level you want.

Together, it looks a bit like this:

from collections import deque

class PriorityQueue:
    def __init__(self, priorities=10):
        self.subqueues = [deque() for _ in range(levels)]

    def enqueue(self, priorty, value):
        self.subqueues[priority].append(value)

    def dequeue(self):
        for queue in self.subqueues:
            try:
                return queue.popleft()
            except IndexError:
                continue