Editor

Python Program to Implement a Priority Queue

Intermediate · Data structures

A priority queue is a queue where each item has a priority, and the most urgent item is removed first, whatever order the items arrived in. Hospitals treat patients this way, and computers use it to schedule tasks. This program uses the `heapq` module, where the smallest number comes out first, so priority 1 is the most urgent.

Program

priority_queue.py
import heapq
tasks = [] # heapq keeps the smallest priority at tasks[0]
def add_task(priority, name):
heapq.heappush(tasks, (priority, name))
print(f"Added: {name} (priority {priority})")
def do_next_task():
if len(tasks) == 0:
print("Nothing to do: the priority queue is empty")
return
priority, name = heapq.heappop(tasks) # removes the smallest priority
print(f"Doing: {name} (priority {priority})")
add_task(3, "Reply to emails")
add_task(1, "Fix the payment bug")
add_task(4, "Plan next week")
add_task(2, "Prepare the slides")
print("Next up:", tasks[0][1]) # peek without removing
while len(tasks) > 0:
do_next_task()
do_next_task() # the queue is empty now
Output
Added: Reply to emails (priority 3)
Added: Fix the payment bug (priority 1)
Added: Plan next week (priority 4)
Added: Prepare the slides (priority 2)
Next up: Fix the payment bug
Doing: Fix the payment bug (priority 1)
Doing: Prepare the slides (priority 2)
Doing: Reply to emails (priority 3)
Doing: Plan next week (priority 4)
Nothing to do: the priority queue is empty

How it works

  1. Each item is stored as a tuple (priority, name), and tuples compare by their first value, so the priority decides the order.
  2. heapq.heappush() adds an item and heapq.heappop() removes the one with the smallest priority, both quickly even for big queues.
  3. The list is kept as a heap, an arrangement in which the smallest item is always at index 0, so tasks[0] peeks at the next task without removing it.
  4. The tasks were added with priorities 3, 1, 4, 2 but come out in the order 1, 2, 3, 4.
  5. Popping from an empty heap would crash, so do_next_task() checks for the empty case first.

Other ways to write it

Using a sorted list

Using a sorted list
queue = []
def add(priority, name):
# Find the first item with a bigger priority and insert before it
i = 0
while i < len(queue) and queue[i][0] <= priority:
i += 1
queue.insert(i, (priority, name))
for priority, name in [(3, "Emails"), (1, "Bug fix"), (2, "Slides")]:
add(priority, name)
print("Queue in order:", queue)
while queue:
print("Doing:", queue.pop(0)[1])
Output
Queue in order: [(1, 'Bug fix'), (2, 'Slides'), (3, 'Emails')]
Doing: Bug fix
Doing: Slides
Doing: Emails

Keeping the list sorted as items arrive also works and is easy to follow, but every insert has to search the list, so heapq is faster for long queues.

Biggest number first

Biggest number first
import heapq
scores = []
for name, score in [("Asha", 82), ("Ben", 95), ("Chitra", 77)]:
heapq.heappush(scores, (-score, name)) # negate so the biggest comes first
while scores:
score, name = heapq.heappop(scores)
print(f"{name}: {-score}")
Output
Ben: 95
Asha: 82
Chitra: 77

heapq always removes the smallest item first, so storing the negative of each score turns that around and the highest score comes out first.

Try it yourself

Add two tasks with the same priority and see which one comes out first.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises