Priority Queue Linked List Implementation

Question

I am new to Python and wanted to make sure my code answers the question for my assignment due.

My Task:

A priority queue is a queue in which each item is assigned a priority and items with a higher priority are removed before those with a lower priority, irrespective of when they were added. Integer values are used for the priorities with a smaller integer value having a higher priority. In an unbounded priority queue, there are no limits on the range of integer values that can be used for the priorities.

• PriorityQueue(): Creates a new empty unbounded priority queue.

• isEmpty(): Returns a boolean value indicating whether the queue is empty.

• length(): Returns the number of items currently in the queue.

• enqueue(item, priority): Adds the given item to the queue by inserting it in the proper position based on the given priority.

• dequeue(): Removes and returns the next item from the queue, which is the item with the highest priority. If two or more items have the same priority, those items are removed in FIFO order. An item cannot be dequeued from an empty queue.

• peek(): Returns a copy of the next item in the queue, without removing the item. The next item is the same value that would be returned by the dequeue operation. An item cannot be dequeued from an empty queue.

My Code:

class Node( object ) :
    def __init__( self, cargo = None, next = None ) :
        self.cargo = cargo
        self.next = next


 # Creates a new empty unbounded priority queue
class PriorityQueue :

     # 
    def __init__( self ) :
        self.length = 0
        self.head = None
        self.last = None

     # Returns a boolean value indicating whether the queue is empty
    def isEmpty( self ) :
        return (self.length == 0)

     # Returns the number of items currently in the queue
    def __len__( self ) :
        return len(self.length)


     # Adds the given item to the queue by inserting it in the proper position 
     # based on the given priority. The new node is appeneded to the end of the
     # linked list
    def enqueue( self, item, priority) :
        newNode = Node(cargo)
        newNode.next = None
        if self.length == 0:
            self.head self.last = newNode
        newNode.next = self.head
        self.head = newNode
        self.last.next = newNode
        self.last = newNode

        temp = self.head
        p = self.head.next
        while p != None :
            if p.cargo > newNode.cargo:
                temp = temp.next
                p = p.next
            break
        newNode.next = temp.next
        temp.next = newNode


     # Removes and returns the next item from the queue, which is the item with 
     # the highest priority. If two or more items have the same priority, those 
     # items are removed in FIFO order. An item cannot be dequeued from an
     # empty queue. The linked list is searched to find the entry with the  
     # highest priority.
    def dequeue( self ) :
        cargo = self.head.cargo
        self.head = self.head.next
        self.length = self.length - 1
        if self.length == 0:
            self.last = None
        return cargo

Answer 1

A Priority Queue is synonymous with a heap so I'm assuming that the implication in this assignment was to implement a maximally efficient data structure.

The optimal implementation is spelled out in Wikipedia: http://en.m.wikipedia.org/wiki/Heap_(data_structure)

If it were me, I would use a tree instead of a list. There is no Node class. A Heap object has two nullable Heap children, and every operation is recursive in nature. Length, for example, would just return each child's length or 1 if no children existed. The other operations would take advantage of the tree's structure in order to return results in logarithmic time.

Answer 2

You are not using a priority variable for prioritizing the order of elements in the queue. Also, there are subtle issues in the code which can be fixed. Please find the below code:-

# Python code to implement Priority Queue using Linked List
# Node class 
class Node:
    def __init__(self, item, priority):
        self.item = item
        self.next = None
        self.priority = priority

class PriorityQueue:
    def __init__(self):
        self.front = self.rear = None

    # Returns a boolean value indicating whether the queue is empty
    def isEmpty(self):
        return self.front == None

    # Adds the given item to the queue by inserting it in the proper 
    # position based on the given priority. The new node is appended to 
    # the end of the linked list
    def enqueue(self, item, priority):
        newNode = Node(item, priority)
        if not self.rear:
            self.front = self.rear = newNode
            return
        if self.front.priority < newNode.priority:
            newNode.next = self.front
            self.front = newNode
            return
        previous = None
        current = self.front
        while(current and newNode.priority < current.priority):
            previous = current
            current = current.next

        if current:
            previous.next = newNode
            newNode.next = current
        else:
            self.rear.next = newNode
            self.rear = newNode

    # Removes and returns the next item from the queue, which is the 
    # item with the highest priority. If two or more items have the 
    # same priority, those items are removed in FIFO order. An item 
    # cannot be dequeued from an empty queue. 
    def dequeue(self):
        if self.isEmpty():
            print('Queue is empty')
            return
        temp = self.front
        self.front = self.front.next
        if self.front == None:
            self.rear = None
        return temp.item