DSA using Python: Priority Queue

Follow me

If you want to understand with Graphical Representation click on it.

You can find the explanatory video at the bottom of this page.

Study Guide: DSA Using Python – Priority Queue

Welcome to this beginner-friendly guide on Priority Queues! This special type of queue is a fundamental concept in computer science, and understanding it will give you a great advantage. Let's dive in and make this topic crystal clear for you.

1. What is a Priority Queue?

Think of a regular line or queue where people are served in the order they arrive. A Priority Queue is a special kind of line where this rule changes. Instead of "first-come, first-served," a Priority Queue handles items based on their importance or priority.

In simple terms: The one with the higher priority gets out first.

It doesn't matter if a high-priority item arrived last; it will still be handled before any lower-priority items that have been waiting longer.

2. Real-Life Examples of Priority Queues

You see Priority Queues in action all the time in the real world.

• Hospital Emergency Room: A patient with a serious injury (high priority) will be treated before a patient with a minor cold (low priority), even if the person with the cold arrived first.
• Airport Check-in: Business class passengers (high priority) often have a separate, faster line and get to board the plane before economy class passengers (lower priority).
• Classroom Questions: A teacher might give the "topper" student the first chance to answer a difficult question, even if other students raised their hands earlier. The topper has a higher priority in this specific situation.
• Computer CPU: The Central Processing Unit (CPU) of a computer handles many tasks. It gives higher priority to important system tasks over less important background tasks to keep your computer running smoothly.

3. Normal Queue vs. Priority Queue

The biggest difference is the rule they follow for letting items out. Let's compare them side-by-side.

Feature	Normal Queue	Priority Queue
Guiding Principle	FIFO (First-In, First-Out)	Highest Priority First
Rule	Whoever gets in line first, gets out first.	Whoever is most important, gets out first.
Example	A line at a movie theater ticket counter.	An emergency room triage system.

4. How "Priority" Works in Python

In programming, we often use numbers to represent priority. In Python's standard implementation of a Priority Queue (heapq), the rule is very simple:

The smallest number has the highest priority.

So, if you have items with priorities 1, 5, 10, and 20, the item with priority 1 is considered the most important and will be the first one to be removed.

5. Using Priority Queues in Python with heapq

Python makes it easy to work with Priority Queues using its built-in heapq library. You don't need to install anything extra!

To get started, you just need two lines of code:

1. import heapq : This tells Python you want to use the special functions for a priority queue.
2. pq = [] : This creates a simple, empty list that heapq will manage as your priority queue.

6. A Simple Code Example

Let's see how to add items and remove the highest-priority item. The two main functions are heappush() to add and heappop() to remove.

# First, we must import the library
import heapq

# Next, we create an empty list to act as our priority queue
pq = []

# Now, let's add some elements using heappush()
# The elements are numbers, which represent both the item and its priority.
heapq.heappush(pq, 10)
heapq.heappush(pq, 5)
heapq.heappush(pq, 20)
heapq.heappush(pq, 1)

# Let's see what our priority queue looks like inside
print(pq)

Output: [1, 5, 20, 10]

Notice that 1 is at the very beginning. That's because it's the smallest number and therefore has the highest priority. The rest of the list is arranged in a special way to be efficient, but it is not fully sorted.

Now, let's remove the most important item using heappop():

# This will remove and return the item with the highest priority (the smallest number)
highest_priority_item = heapq.heappop(pq)
print(highest_priority_item)

Output: 1

After this operation, the number 1 is gone from our priority queue.

7. Visualizing the Changes

Let's track how our list pq changes with each step.

1. Start: pq = []
2. heapq.heappush(pq, 10) → pq becomes [10]
3. heapq.heappush(pq, 5) → pq becomes [5, 10]
4. heapq.heappush(pq, 20) → pq becomes [5, 10, 20]
5. heapq.heappush(pq, 1) → pq becomes [1, 5, 20, 10]
6. heapq.heappop(pq) → returns 1, and pq becomes [5, 10, 20]

8. Common Beginner Mistakes

1. Assuming the List is Fully Sorted: A common mistake is to look at the output [1, 5, 20, 10] and think the priority queue is broken because it's not sorted like [1, 5, 10, 20]. Remember, heapq only guarantees that the first element (pq[0]) is the smallest. The rest of the list is organized for speed, not for human readability.
2. Forgetting to import heapq: If you try to use heappush or heappop without importing the library first, your code will crash.
3. Using the Wrong Function Names: Remember the functions are heapq.heappush(list, item) and heapq.heappop(list). Don't try to call them like list.add(item).

9. Where Are Priority Queues Used?

Priority Queues are incredibly useful and are found in many real-world applications:

• CPU and Job Scheduling: Deciding which computer process to run next.
• Mapping Services (like Google Maps): Finding the shortest path between two points (used in Dijkstra's algorithm).
• AI Algorithms: Used in pathfinding algorithms like A*.
• Task Manager Apps: Organizing to-do lists by priority.
• Data Compression: A key part of Huffman Coding, which is used to make files smaller.
• Hospital Management Systems: Managing patient queues digitally.

10. Easy Practice Questions

Test your knowledge with these quick questions.

1. What does FIFO stand for?
2. In a normal queue, if person A arrives before person B, who is served first?
3. In a hospital priority queue, who is treated first: a patient with a broken arm or a patient with a cold?
4. What is the one-line definition of a Priority Queue?
5. Which Python library do you need to import to use Priority Queues?
6. What function do you use to add an element to a heapq priority queue?
7. What function do you use to remove the highest priority element?
8. If you have the priorities [15, 8, 22], which one has the highest priority in Python's heapq?
9. Does heapq keep the entire list sorted at all times? (Yes/No)
10. Name one real-world application of a Priority Queue mentioned in this guide.

--------------------------------------------------------------------------------

Quiz: Test Your Understanding

Provide a short answer (2-3 sentences) for each of the following questions.

1. What is the fundamental difference between how a Normal Queue and a Priority Queue decide which element to remove next?
2. Explain the hospital emergency room example using the concept of "priority."
3. Why is a Priority Queue a better choice than a Normal Queue for managing tasks in a computer's CPU?
4. In the Python heapq library, what does it mean for an element to have the "highest priority"?
5. What are the two primary operations for a priority queue, and what does each one do?
6. If you add the numbers 50, 25, and 100 to an empty priority queue in that order, which number will heappop remove first and why?
7. A student in a classroom raises their hand last but is known to be the "topper." The teacher calls on them first. How does this scenario model a Priority Queue?
8. Looking at the list [1, 5, 20, 10], which is the internal state of a priority queue, why is it incorrect to assume the entire list should be sorted?
9. Describe the airport check-in example and identify which group of passengers has higher priority.
10. Other than scheduling tasks, name two different real-world systems or algorithms where Priority Queues are used.

Answer Key

1. A Normal Queue uses a "First-In, First-Out" (FIFO) principle, where the oldest element is removed first. A Priority Queue removes the element with the highest priority, regardless of when it was added.
2. In a hospital, patients are assigned a priority based on the seriousness of their condition. A patient with a life-threatening injury has a higher priority and is treated before someone with a minor issue, even if the latter arrived earlier.
3. A Priority Queue is better for CPU scheduling because some tasks are more critical to the computer's operation than others. It allows the CPU to execute important system tasks immediately, ensuring the computer remains stable and responsive.
4. In Python's heapq library, the element with the smallest numerical value is considered to have the "highest priority." This means if you have numbers 10 and 5, the number 5 has a higher priority.
5. The two primary operations are heappush() and heappop(). heappush() is used to add a new element to the priority queue. heappop() is used to remove and return the element that currently has the highest priority.
6. The heappop function will remove the number 25 first. This is because in Python's heapq, the smallest number has the highest priority, and 25 is the smallest among 50, 25, and 100.
7. This models a Priority Queue because the student's status as a "topper" gives them a higher priority than their arrival time (when they raised their hand). The teacher prioritizes the "topper" student over others, just as a Priority Queue processes high-priority items first.
8. It's incorrect because the heapq data structure only guarantees that the first element is the one with the highest priority (the smallest). The rest of the elements are arranged in a specific heap structure that is efficient for adding and removing items, not for being fully sorted.
9. In the airport check-in example, different classes of passengers represent different priority levels. Business class passengers have a higher priority, allowing them to check-in and board before economy class passengers.
10. Two other uses for Priority Queues are in Google Maps for finding the shortest path and in data compression algorithms like Huffman Coding.

Suggested Long-Answer Questions

These are for you to think about. No answers are provided.

1. Imagine you are designing a task manager application. Explain how you would use a Priority Queue to manage tasks labeled "High," "Medium," and "Low." How would you represent these priorities with numbers for Python's heapq?
2. Compare and contrast the real-life examples of a hospital emergency room and a line at a grocery store. Explain in detail why one is a Priority Queue and one is a Normal Queue.
3. Describe a scenario where using a Normal Queue when a Priority Queue is needed would cause significant problems.
4. The heapq library in Python is called a "min-heap" because it always keeps the minimum value at the top. How might you change your approach if you needed a "max-heap," where the largest number had the highest priority?
5. Explain the statement: "A Priority Queue is an abstract data type, while a heap is a data structure used to implement it."

--------------------------------------------------------------------------------

Glossary

Term	Definition
Priority Queue	A special type of queue that processes elements based on their priority level, not their arrival order.
Normal Queue	A standard queue that processes elements based on the "First-In, First-Out" (FIFO) principle.
FIFO	Stands for "First-In, First-Out." The rule that the first item to enter a queue is the first item to leave it.
Priority	A value assigned to an element that determines its importance or rank in the queue.
heapq	A built-in Python library that provides tools for creating and working with Priority Queues (specifically, min-heaps).
heappush()	The heapq function used to add a new element into the priority queue while maintaining the heap structure.
heappop()	The heapq function used to remove and return the element with the highest priority (the smallest value) from the queue.
CPU Scheduling	The process of determining which computer task or process the Central Processing Unit (CPU) should execute next.