Priority Queue Introduction and Concept in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this priority queue insertion sequence?

Consider a min-priority queue implemented using a heap. Insert the elements 5, 3, 6, 2 in this order. What is the state of the heap array after all insertions?

DSA Python

import heapq
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 3)
heapq.heappush(pq, 6)
heapq.heappush(pq, 2)
print(pq)

A [2, 3, 6, 5]

B [3, 2, 6, 5]

C [2, 3, 5, 6]

D [5, 3, 6, 2]

💡 Hint

Remember that heapq in Python maintains the smallest element at index 0.

The heap after inserting 5, 3, 6, 2 will reorder to keep the smallest element at the root. The final heap array is [2, 3, 6, 5].

🧠 Conceptual

intermediate

Which operation does NOT belong to a priority queue?

Select the operation that is NOT typically supported by a priority queue.

A Insert an element with a priority

B Extract the element with the highest priority

C Peek at the element with the highest priority without removing it

D Search for an element by value

💡 Hint

Priority queues focus on priority-based access, not searching by value.

Priority queues do not support searching for elements by value efficiently; they focus on insertion and extracting the highest priority element.

🔧 Debug

advanced

What error does this priority queue code raise?

Identify the error raised by this code snippet using Python's heapq module.

DSA Python

import heapq
pq = []
heapq.heappush(pq, 10)
heapq.heappop(pq)
heapq.heappop(pq)

A IndexError: index out of range

B KeyError: key not found

C TypeError: unsupported operand type(s)

D No error, returns None

💡 Hint

Consider what happens when popping from an empty heap.

After popping the only element, the next pop tries to remove from an empty list, causing IndexError.

🚀 Application

advanced

What is the output after these priority queue operations?

Given a max-priority queue implemented by negating values in a min-heap, what is the output after these operations? Operations: Insert 4, Insert 7, Insert 1, Extract max, Insert 5 Print the remaining heap array (negated back to positive values).

DSA Python

import heapq
pq = []
heapq.heappush(pq, -4)
heapq.heappush(pq, -7)
heapq.heappush(pq, -1)
max_val = -heapq.heappop(pq)
heapq.heappush(pq, -5)
result = [-x for x in pq]
print(sorted(result))

A [1, 5, 7]

B [4, 5, 7]

C [1, 4, 5]

D [1, 4, 7]

💡 Hint

Remember to negate values back to positive and sort to visualize the heap contents.

After extracting max (7), the heap contains 4, 1, and after inserting 5, the heap has 1, 4, 5.

🧠 Conceptual

expert

Which data structure property is essential for a priority queue implemented as a heap?

Select the property that must always hold true in a heap-based priority queue.

A Balanced AVL tree property

B Complete binary tree property

C Linked list ordering property

D Binary search tree property

💡 Hint

Heaps are stored as arrays and must be complete binary trees.

A heap must be a complete binary tree to maintain efficient insertion and extraction operations.

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