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?

Priority of elements in a queue

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

AI Code Explainer

Paste any Python code below and get a plain-English explanation.

Python Programming

17-3. Priority Queue

How it works?

Priority Queue Implementation