Priority Queue Introduction and Concept in DSA Python

Mental Model

A priority queue is like a line where people with higher importance get served first, no matter when they arrive.

Analogy: Imagine a hospital emergency room where patients with more serious conditions are treated before others, even if they arrived later.

Priority Queue:
[10] -> [5] -> [3] -> [1] -> null
↑ front (highest priority)

Dry Run Walkthrough

Input: Insert values 3, 10, 5 into an empty priority queue (higher number means higher priority). Then remove the highest priority element.

Goal: Show how elements are added and removed so that the highest priority is always served first.

Step 1: Insert 3 into empty queue

[3] -> null ↑ front

Why: First element becomes the front as it is the only one

Step 2: Insert 10, which has higher priority than 3

[10] -> [3] -> null ↑ front

Why: 10 goes before 3 because it has higher priority

Step 3: Insert 5, which has priority between 10 and 3

[10] -> [5] -> [3] -> null ↑ front

Why: 5 is placed between 10 and 3 to keep order by priority

Step 4: Remove element from front (highest priority)

[5] -> [3] -> null ↑ front

Why: 10 is removed because it has the highest priority

Result:

[5] -> [3] -> null ↑ front
Removed element: 10

Annotated Code

DSA Python

class Node:
    def __init__(self, value, priority):
        self.value = value
        self.priority = priority
        self.next = None

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

    def insert(self, value, priority):
        new_node = Node(value, priority)
        if self.front is None or priority > self.front.priority:
            new_node.next = self.front
            self.front = new_node
            return
        current = self.front
        while current.next and current.next.priority >= priority:
            current = current.next
        new_node.next = current.next
        current.next = new_node

    def remove(self):
        if self.front is None:
            return None
        removed_value = self.front.value
        self.front = self.front.next
        return removed_value

    def __str__(self):
        result = []
        current = self.front
        while current:
            result.append(str(current.value))
            current = current.next
        return ' -> '.join(result) + ' -> null'

# Driver code
pq = PriorityQueue()
pq.insert(3, 3)
pq.insert(10, 10)
pq.insert(5, 5)
print(pq)
removed = pq.remove()
print(pq)
print(f'Removed element: {removed}')

if self.front is None or priority > self.front.priority:

Check if new node should be front because queue is empty or new priority is highest

while current.next and current.next.priority >= priority:

Traverse to find correct position to insert new node maintaining priority order

removed_value = self.front.value

Store value of front node to return after removal

self.front = self.front.next

Remove front node by moving front pointer to next node

Output

10 -> 5 -> 3 -> null

5 -> 3 -> null

Removed element: 10

Complexity Analysis

Time: O(n) because in worst case we traverse the whole queue to insert an element in correct position

Space: O(n) because we store all elements in linked nodes

vs Alternative: Compared to a simple queue where insertion is O(1) but removal of highest priority is O(n), priority queue keeps removal O(1) but insertion O(n)

Edge Cases

Empty queue when removing

Returns None safely without error

DSA Python

if self.front is None:
            return None

Insert element with priority equal to existing nodes

Inserted after nodes with same priority to maintain stable order

DSA Python

while current.next and current.next.priority >= priority:

Insert into empty queue

New node becomes front

DSA Python

if self.front is None or priority > self.front.priority:

When to Use This Pattern

When you need to always process the most important item first, use a priority queue to keep elements sorted by priority automatically.

Common Mistakes

Mistake: Inserting new element at the end regardless of priority
Fix: Traverse and insert at correct position based on priority

Mistake: Removing from the end instead of front
Fix: Always remove from front to get highest priority element

Summary

A priority queue stores elements so that the highest priority is always at the front.

Use it when you want to process items by importance, not just arrival order.

The key is to insert elements in order so removal is always the highest priority.

Practice

1. What is the main feature of a priority queue compared to a regular queue?

easy

A. It does not allow insertion after creation

B. Elements are always dequeued in the order they were inserted

C. It only stores elements of the same value

D. Elements are dequeued based on their priority, not just order of insertion

Solution

1. Step 1: Understand queue behavior

   A regular queue removes elements in the order they were added (FIFO).

2. Step 2: Understand priority queue behavior

   A priority queue removes elements based on priority, not just order.

3. Final Answer:

   Elements are dequeued based on their priority, not just order of insertion -> Option D

4. Quick Check:

   Priority queue = priority-based removal [OK]

Hint: Priority queue removes highest priority first, not oldest [OK]

Common Mistakes:

• Confusing priority queue with FIFO queue
• Thinking priority queue only stores equal values
• Assuming no insertion allowed after creation

2. Which of the following is the correct way to import and create a min-priority queue using Python's heapq module?

easy

A. from queue import PriorityQueue; pq = PriorityQueue()

B. import heapq; pq = []

C. import heapq; pq = heapq.PriorityQueue()

D. import queue; pq = queue.heapq()

Solution

1. Step 1: Identify correct module for heapq min-priority queue

   Python's heapq module implements min-heap using lists.

2. Step 2: Check import and creation syntax

   import heapq; pq = [] correctly imports heapq and creates an empty list to use as heap.

3. Final Answer:

   import heapq; pq = [] -> Option B

4. Quick Check:

   heapq module with empty list = correct [OK]

Hint: heapq uses empty list [] for min-heap [OK]

Common Mistakes:

• Confusing heapq (functions) with PriorityQueue class
• Trying to call heapq.PriorityQueue() which doesn't exist
• Wrong import statements

3. What will be the output of the following code?

import heapq
pq = []
heapq.heappush(pq, 20)
heapq.heappush(pq, 5)
heapq.heappush(pq, 15)
print(heapq.heappop(pq))

medium

A. 5

B. 20

C. 15

D. Error

Solution

1. Step 1: Understand heapq behavior

   heapq creates a min-heap, so smallest element is popped first.

2. Step 2: Trace the pushes and pop

   Elements pushed: 20, 5, 15. The smallest is 5, so heappop returns 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Min-heap pop = smallest element = 5 [OK]

Hint: heapq pops smallest element first [OK]

Common Mistakes:

• Thinking heapq pops largest element
• Confusing push order with pop order
• Expecting error due to empty heap

4. Identify the error in the following code that tries to implement a max-priority queue using heapq:

import heapq
pq = []
heapq.heappush(pq, 10)
heapq.heappush(pq, 30)
heapq.heappush(pq, 20)
max_val = heapq.heappop(pq)
print(max_val)

medium

A. pq should be a list of tuples, not integers

B. heapq does not support push operation

C. heapq.heappop returns the smallest element, not the largest

D. Missing call to heapq.heapify before pushing

Solution

1. Step 1: Understand heapq default behavior

   heapq implements a min-heap, so heappop returns smallest element.

2. Step 2: Check code for max-priority queue logic

   The code pushes values directly and pops, expecting max but gets min.

3. Final Answer:

   heapq.heappop returns the smallest element, not the largest -> Option C

4. Quick Check:

   heapq pop = smallest, not max [OK]

Hint: heapq pops smallest; invert values for max-heap [OK]

Common Mistakes:

• Expecting heappop to return max without inversion
• Not using negative values to simulate max-heap
• Assuming heapq needs heapify before every push

5. You want to implement a max-priority queue using Python's heapq module. Which approach correctly achieves this?

hard

A. Push negative values and pop normally, then negate again

B. Use heapq as is, it supports max-heap by default

C. Sort the list after every push to get max element

D. Use a separate max() function after popping from heapq

Solution

1. Step 1: Understand heapq default behavior

   heapq is a min-heap, so it pops smallest element by default.

2. Step 2: Implement max-heap using negation

   By pushing negative values, the smallest negative corresponds to largest original value. Pop and negate again to get max.

3. Final Answer:

   Push negative values and pop normally, then negate again -> Option A

4. Quick Check:

   Negate values to simulate max-heap with heapq [OK]

Hint: Invert values (negate) to use min-heap as max-heap [OK]

Common Mistakes:

• Assuming heapq supports max-heap natively
• Sorting list after every push is inefficient
• Using max() after pop breaks priority queue logic