17-3. Priority Queue

In a standard queue described in the previous section, elements are managed on a First-In, First-Out basis, where they are added to the back and removed from the front.

However, a priority queue assigns priority levels to its elements. When accessing elements, those with the highest priority are dealt with first, reflecting a largest-in, first-out behavior. For instance, in a hospital's emergency room, in a hospital's emergency room, patients are prioritized with numbers, ensuring that the most urgent cases receive immediate attention.

How it works?

The item with the highest priority is positioned at the forefront to be served first.

Priority Queue Implementation

Using a List:

Let's suppose that 4 represents the highest priority, while 1 signifies the lowest priority.

### Using a List

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

def enqueue(self, priority, item):
        self.queue.append((priority, item))
        self.queue.sort(reverse=True)  # Sort in descending order of priority

def dequeue(self):
          if not self.isEmpty():
               return self.queue.pop(0)
          else:
               raise IndexError("Cannot dequeue from an empty priorityqueue")

def getSize(self):
          return len(self.queue)

def isEmpty(self):
          return len(self.queue) == 0
    
def main():
      pq = PriorityQueue()
      pq.enqueue(2, "John")
      pq.enqueue(3, "Tom")
      pq.enqueue(1, "Kelly")
      pq.enqueue(4, "Jane")

print("Size of queue:", pq.getSize())
      print("Is queue empty?", pq.isEmpty())

print("Dequeue:", pq.dequeue())
      print("Dequeue:", pq.dequeue())
      print("Dequeue:", pq.dequeue())
      print("Dequeue:", pq.dequeue())

print("Is queue empty?", pq.isEmpty())

main()

Output:

Size of queue: 4

Is queue empty? False

Dequeue: (4, 'Jane')

Dequeue: (3, 'Tom')

Dequeue: (2, 'John')

Dequeue: (1, 'Kelly')

Is queue empty? True

Using a heapq:

Let's suppose that 4 represents the highest priority, while 1 signifies the lowest priority.

Output:

Size of queue: 4

Is queue empty? False

Dequeue: Jane

Dequeue: Tom

Dequeue: John

Dequeue: Kelly

Is queue empty? True

Using a PriorityQueue:

In this scenario, let's designate 4 as the highest priority and 1 as the lowest priority.

Output:

Size of queue: 4

Is queue empty? False

Dequeue: Jane

Dequeue: Tom

Dequeue: John

Dequeue: Kelly

Is queue empty? True

Last updated: April 23, 2025

Python Programming

17-3. Priority Queue