Skip to content
Tutorials Center
My learning

Topics

Lesson 51 of 225 ยท Stacks and Queues

Priority Queues

Learn priority queues in Python: the concept, unsorted and sorted list versions, a preview of heaps, heapq vs queue.PriorityQueue and a task scheduler example.

In an ordinary queue the item that waited longest goes first. In many real systems that is the wrong rule. An emergency room treats the most serious patient first, not the one who arrived first. An operating system runs the highest-priority process first. A navigation app expands the closest unexplored intersection first.

A priority queue is an abstract data type where every item has a priority, and the item removed next is always the one with the best priority (usually the smallest number, meaning "most urgent", or the largest). Arrival order only matters as a tie-breaker, if at all.

The interface

Operation Meaning
push(item, priority) insert an item with a priority
pop() remove and return the item with the best priority
peek() look at the best item without removing it
len(pq) how many items are waiting

Notice what is not offered: searching for arbitrary items, or iterating in sorted order. A priority queue only promises to hand you the best item next. That weaker promise is exactly what makes a fast implementation possible.

In this lesson, a smaller number means higher priority (a "min-priority queue"), the convention used by Python's heapq. A max-priority queue just flips the comparison.

Implementation 1: an unsorted list

Store (priority, item) pairs in a list in any order.

  • push: append to the list. O(1).
  • pop: scan the whole list to find the minimum, then remove it. O(n).

Implementation 2: a sorted list

Keep the list sorted by priority, so the best item is always at a known end.

  • push: find the right spot and insert, shifting later items. O(n) (binary search finds the spot in O(log n), but inserting still shifts).
  • pop: remove from the end (keep the list in descending order so the best is last). O(1).
Python Two list-based priority queues

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both give the right order. One is cheap to fill and expensive to drain; the other is the opposite. If you do n pushes and n pops, either way you pay O(nยฒ) in total. Can we do better for both operations at once?

Preview: the binary heap

Yes. A binary heap stores the items in a nearly sorted tree, packed into a plain array, such that the best item is always at index 0. Both push and pop take O(log n), and peek is O(1). We build one from scratch in Binary Heaps.

Implementation push pop peek
Unsorted list O(1) O(n) O(n)
Sorted list O(n) O(1) O(1)
Binary heap O(log n) O(log n) O(1)

For n = 1,000,000 items, log n is about 20, so a heap does roughly 20 steps where a list does up to a million.

Python tool 1: heapq

The heapq module turns an ordinary list into a min-heap. You push and pop with functions rather than methods.

Python A priority queue with heapq

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Observe how the two priority-1 tasks come out: "answer security email" before "fix outage". When priorities tie, Python compares the next tuple element, the strings, alphabetically. That can surprise you, and it can crash: if the second elements cannot be compared (for example dictionaries or custom objects), a tie in priority raises TypeError. The standard fix is a tie-breaking counter, shown below.

Python tool 2: queue.PriorityQueue

queue.PriorityQueue is a wrapper around heapq with put and get methods. It adds thread-safe locking so several threads can share it. The price is extra overhead per call.

Python queue.PriorityQueue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

heapq queue.PriorityQueue
Interface functions on a list object with put/get
Thread-safe no yes (locks)
Speed faster slower
Peek pq[0] none (no public peek)
Use for algorithms, single thread producer/consumer between threads

For algorithm problems (Dijkstra, top-k, merging), use heapq. Reach for PriorityQueue only when threads share the queue.

Stable ordering with a counter

A neat property of a plain queue is that equal items come out in arrival order. A heap does not guarantee that. To get first come, first served among equal priorities, add an increasing counter as the second tuple element. It also guarantees the items themselves are never compared.

Python Tie-breaking counter keeps arrival order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Max-priority queues

heapq is a min-heap only. To get the largest first, store negated priorities, as the sorted list above did: push (-priority, item) and negate again when popping. For non-numeric keys, wrap the key in a small class with a reversed __lt__.

Python Largest first by negating the priority

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Example: a task scheduler

A scheduler holds tasks with a priority and runs the most urgent one each turn. New tasks may arrive while others wait, which is exactly where a priority queue beats re-sorting a list every time.

Python Simple priority task scheduler

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The late arrival restart server runs before older, less urgent work. The two priority-3 tasks keep their submission order thanks to the counter.

Where priority queues are used

Common mistakes

  • Assuming heapq lists are sorted. Only pq[0] is guaranteed to be the minimum. Printing the list shows heap order, not sorted order.
  • Forgetting that it is a min-heap, then getting smallest-first when you wanted largest-first.
  • Comparing uncomparable items on priority ties. Add a counter.
  • Modifying priorities in place. Changing a tuple's priority inside the list breaks the heap property. Push a new entry instead and ignore stale ones when popped ("lazy deletion").
  • Using a sorted list for a heavy workload and wondering why inserts are slow.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which item does a priority queue remove next?

    That is the defining rule: pop returns the item with the best priority, regardless of arrival order.
  2. 2. In an unsorted-list priority queue, what are the costs of push and pop?

    Pushing just appends, but popping must scan all the items to find the best one.
  3. 3. What are the costs of push and pop in a binary heap?

    A heap is a complete binary tree of height about log n, and both operations move an item along one root-to-leaf path.
  4. 4. Why add a counter to heap entries like (priority, counter, item)?

    When priorities tie, the counter decides, so the items themselves (which may not be comparable) are never compared.
  5. 5. How do you get the largest value first from heapq?

    heapq only provides a min-heap, so negating numeric priorities flips the order.

Summary

  • A priority queue always returns the item with the best priority; arrival order is irrelevant except as a tie-breaker.
  • Unsorted and sorted lists make one operation O(1) and the other O(n); a binary heap makes both O(log n).
  • In Python use heapq (fast, min-heap, not thread-safe) or queue.PriorityQueue (thread-safe wrapper).
  • Add (priority, counter, item) tuples to keep equal priorities in arrival order and avoid comparing items.
  • Negate numbers for a max-priority queue; never edit a priority in place.
  • The heap inside is built from scratch in Binary Heaps, later in the tutorial.

Next: Hash Tables