Python Implementing a Priority Queue

Question

I am trying to make a priority queue without using the Queue module. I have made a class PriorityQueue() and I am trying to create a mk function that takes no arguments and returns an empty queue but can't seem to figure out how. my task function is here:

class Task():

    __slots__ = ('name', priority)

def mkTask(myName, myPriority):
    t = Task()
    t.name = myName
    t.priority = myPriority
    return t

What I have so far for my PriorityQueue class and a function to check if the queue is empty is this:

class PriorityQueue():
    def __init__(queue):
        queue.length = 0
        queue.first = None
        queue.last = None

def is_empty(queue):
    return(queue.length == 0)

I can't seem to figure out how to create an instance of the Queue and insert elements of a specific Task into the Queue.

http://stackoverflow.com/questions/19744829/python-priority-queue-implementation This is the same as this — Naib, Nov 02 '13 at 18:16

score 1 · Answer 1 · answered Nov 02 '13 at 18:24

A priority queue is often implemented using a heap, and here's such an implementation. Note, that the heap implementation in Python returns the smallest thing in the heap, so I negate the priority so that highest priority things get popped first.

import heapq

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

    def push(self, priority, x):
        heapq.heappush(self.items, (-priority, x))

    def pop(self):
        _, x = heapq.heappop(self.items)
        return x

    def empty(self):
        return not self.items

Python Implementing a Priority Queue

1 Answers1