What Is a Priority Queue: Definition, Example, and Uses

A priority queue is a special type of data structure where each element has a priority, and elements are served based on their priority rather than their order of insertion. The element with the highest priority is always removed first. It is commonly used in tasks like scheduling and managing resources.

How It Works

A priority queue works like a line where people with urgent needs get served first, regardless of when they arrived. Imagine a hospital emergency room where patients with more serious conditions are treated before others who came earlier but have less urgent issues.

In a priority queue, each item has a priority value. When you add items, they are placed according to their priority, not just at the end of the line. When you remove an item, the one with the highest priority comes out first. This makes priority queues different from regular queues, which follow a simple first-in, first-out order.

Example

This example shows how to use a priority queue in Python using the built-in heapq module. It adds tasks with different priorities and removes them in order of highest priority first.

python

import heapq

# Create an empty priority queue
priority_queue = []

# Add tasks with priorities (lower number means higher priority)
heapq.heappush(priority_queue, (2, 'Clean the house'))
heapq.heappush(priority_queue, (1, 'Pay bills'))
heapq.heappush(priority_queue, (3, 'Do homework'))

# Remove tasks in priority order
while priority_queue:
    priority, task = heapq.heappop(priority_queue)
    print(f"Task: {task}, Priority: {priority}")

Output

Task: Pay bills, Priority: 1
Task: Clean the house, Priority: 2
Task: Do homework, Priority: 3

When to Use

Use a priority queue when you need to process items based on importance rather than arrival time. Common uses include:

• Task scheduling in operating systems, where urgent tasks run before others.
• Managing events in simulations, where events with earlier times happen first.
• Handling requests in network routers, prioritizing critical data packets.
• Algorithms like Dijkstra's shortest path, which always pick the next closest node.

Priority queues help make systems efficient by focusing on what matters most first.

Key Points

• A priority queue orders elements by priority, not just arrival order.
• The highest priority element is always removed first.
• It can be implemented using heaps for efficient operations.
• Widely used in scheduling, simulations, and graph algorithms.

Key Takeaways

A priority queue serves elements based on priority, not insertion order.

The highest priority element is always accessed or removed first.

Heaps are a common way to implement priority queues efficiently.

Use priority queues for scheduling, simulations, and algorithm optimizations.