Priority Queues in Python

A Priority Queue is an abstract data structure that is used to maintain a queue of data elements where each element is assigned a priority of precedence.

It is similar to a queue in implementation, but the only difference lies in the fact that Priority Queues have a certain priority attached to each of its elements. This priority is followed when the queue is dequeued.

Priority Queues are dynamic data structures. Also, any type of data can be stored in a Priority Queue.
priority-queue

Priority Queue nodes contain three fields; the data field, the priority field, and the link field which holds the link to the next element in the queue.

Factors that govern a Priority Queue
  1. An element of higher priority will always be dequeued before an element with lower priority
  2. Two elements having the same priority will be dequeued in First In First Out (FIFO) order

Characteristics of Priority Queues

  • Ordered - Elements are arranged in a certain order
  • Mutable - Elements can be added/ deleted/ modified
  • Dynamic - The data structure is dynamic ie. can be extended and shortened
  • Any type of data can be stored
  • Elements in the queue follow a certain priority of precedence

Implementing a Priority Queue in Python

The implementation of a Priority Queue in Python is quite similar to the implementation of a normal Queue. The only difference lies in the fact that in this case, the priorities of the individual elements require to be considered.

A Priority Queue in Python can be implemented by following these steps.

  1. Definition of the Node class in Priority Queues also has an extra field called priority, which stores the priority factor for each element of the Queue
    class Node:
        def __init__(self, val, priority):
            self.value = val
            self.priority = priority
            self.next = None​
  2. Defining the Priority Queue class
    class Pqueue:​
  3. Initializing the front and rear pointers for the Priority Queue
        def __init__(self):
            self.Front = None
            self.Rear = None​
  4. Definition of the enqueue() method in a Priority Queue differs from a normal queue with respect to the priority factor that needs to be considered while adding elements to the queue
    def enqueue(self, val, priority=None):
    1. Checking whether or not a Priority Queue is empty and initializing it
              if self.empty() is True:
                  self.Front = Node(val, priority)
                  self.Rear = self.Front
                  return​
    2. Creating the Node to be added
      inst = Node(val, priority)​
    3. Adding the Node to the Priority Queue based on its priority value, and in case of similar priority, according to the First in First out (FIFO) precedence
              if inst.priority < self.Front.priority:
                  inst.next = self.Front
                  self.Front = inst
              elif inst.priority >= self.Rear.priority:
                  self.Rear.next = inst
                  self.Rear = self.Rear.next
              elif inst.priority == self.Front.priority:
                  n = self.Front.next
                  f = self.Front
                  while n.priority == inst.priority:
                      n = n.next
                      f = f.next
                  f.next = inst
                  f.next.next = n
              else:
                  f = self.Front.next
                  n = f.next
                  while n.priority <= inst.priority:
                      n = n.next
                      f = f.next
                  f.next = inst
                  f.next.next = n​
  5. Defining the dequeue() method which is used to remove elements from the Priority Queue according to their priority values
        def dequeue(self):
            if self.empty() is True:
                print("Queue is empty")
                return -1
            elif self.Front == self.Rear:
                temp = self.Front.value
                self.Front = None
                self.Rear = None
                return temp
            else:
                temp = self.Front.value
                self.Front = self.Front.next
                return temp​
  6. Defining the front() method which returns the front pointer of the Priority Queue
        def front(self):
            if self.empty() is True:
                print("Queue empty")
                return -1
            else:
                return self.Front.value​
  7. Defining the rear() method which returns the rear pointer element of the Priority Queue
        def rear(self):
            if self.empty() is True:
                print("Queue empty")
                return -1
            else:
                return self.Rear.value​
  8. Defining the empty() method which is used to check whether or not the Priority Queue is empty
        def empty(self):
            if self.Rear is None:
                return True
            else:
                return False​
  9. The display() in the Priority Queue differs by the fact that the priorities require to be printed alongside the data values in a user-comprehendible format
        def display(self):
            print("The Queue")
            if self.empty() is True:
                print("Queue empty")
            elif self.Front == self.Rear:
                print("val priority")
                print(self.Front.value, "\t", self.Front.priority,  "<== FRONT <== REAR")
            else:
                i = self.Front.next
                print("val priority")
                print(self.Front.value, "\t", self.Front.priority, "<== FRONT")
                while i is not self.Rear:
                    print(i.value, "\t", i.priority)
                    i = i.next
                print(self.Rear.value, "\t", self.Rear.priority, "<== REAR")
            print("Queue Over")
  10. The Python 3 code implementing a Priority Queue, using the object-oriented characteristic, implementing the methods manipulating it, and creating an instance of it is as follows
    class Node:
        def __init__(self, val, priority):
            self.value = val
            self.priority = priority
            self.next = None
    
    class Pqueue:
        def __init__(self):
            self.Front = None
            self.Rear = None
    
        def enqueue(self, val, priority=None):
            if self.empty() is True:
                self.Front = Node(val, priority)
                self.Rear = self.Front
                return
            inst = Node(val, priority)
            if inst.priority < self.Front.priority:
                inst.next = self.Front
                self.Front = inst
            elif inst.priority >= self.Rear.priority:
                self.Rear.next = inst
                self.Rear = self.Rear.next
            elif inst.priority == self.Front.priority:
                n = self.Front.next
                f = self.Front
                while n.priority == inst.priority:
                    n = n.next
                    f = f.next
                f.next = inst
                f.next.next = n
            else:
                f = self.Front.next
                n = f.next
                while n.priority <= inst.priority:
                    n = n.next
                    f = f.next
                f.next = inst
                f.next.next = n
    
        def dequeue(self):
            if self.empty() is True:
                print("Queue is empty")
                return -1
            elif self.Front == self.Rear:
                temp = self.Front.value
                self.Front = None
                self.Rear = None
                return temp
            else:
                temp = self.Front.value
                self.Front = self.Front.next
                return temp
    
        def front(self):
            if self.empty() is True:
                print("Queue empty")
                return -1
            else:
                return self.Front.value
    
        def rear(self):
            if self.empty() is True:
                print("Queue empty")
                return -1
            else:
                return self.Rear.value
    
        def empty(self):
            if self.Rear is None:
                return True
            else:
                return False
    
        def display(self):
            print("The Queue")
            if self.empty() is True:
                print("Queue empty")
            elif self.Front == self.Rear:
                print("val priority")
                print(self.Front.value, "\t", self.Front.priority,  "<== FRONT <== REAR")
            else:
                i = self.Front.next
                print("val priority")
                print(self.Front.value, "\t", self.Front.priority, "<== FRONT")
                while i is not self.Rear:
                    print(i.value, "\t", i.priority)
                    i = i.next
                print(self.Rear.value, "\t", self.Rear.priority, "<== REAR")
            print("Queue Over")
    
    a = Pqueue()
    a.enqueue(1, 2)
    a.enqueue(2, 1)
    a.enqueue(5, 1)
    a.enqueue(9, 0)
    a.enqueue(10, 3)
    a.display()
    print(a.dequeue())
    a.display()
    print(a.front())
    a.dequeue()
    print(a.rear())
    a.display()
    a.dequeue()
    a.dequeue()
    a.display()
    a.dequeue()
    a.display()

    the output being

    The Queue
    val priority
    9 	 0 <== FRONT
    2 	 1
    5 	 1
    1 	 2
    10 	 3 <== REAR
    Queue Over
    9
    The Queue
    val priority
    2 	 1 <== FRONT
    5 	 1
    1 	 2
    10 	 3 <== REAR
    Queue Over
    2
    10
    The Queue
    val priority
    5 	 1 <== FRONT
    1 	 2
    10 	 3 <== REAR
    Queue Over
    The Queue
    val priority
    10 	 3 <== FRONT <== REAR
    Queue Over
    The Queue
    Queue empty
    Queue Over

Advantages and Disadvantages of Priority Queues

Advantages
  • The priority factor enables weighted advantage of certain nodes over others
  • Easy to correct
  • Easy to implement
  • Dynamic memory allocation enabled
Disadvantages
  • Memory overhead
  • Complex structure
  • Complex manipulation processes

Applications of Priority Queues

  • CPU priority scheduling
  • Solving Dijkstra's shortest path algorithm
  • Solving the Prim's Minimum Spanning Tree model
  • Data compression using Huffman codes
  • A*search algorithm
0 results
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions