Priority Queue

A priority queue manages a changing set of candidates and returns the candidate that is currently best according to a chosen priority. This document explains that behavior before introducing Python’s heapq, so the implementation can be understood as one way to provide the behavior rather than as the definition of a priority queue.

Why a Normal Queue Is Not Enough

A normal queue follows first in, first out order, usually shortened to FIFO. The item that entered earliest leaves first.

Suppose these tasks arrive in order:

"slow" with priority 5
"urgent" with priority 1
"normal" with priority 3

A normal queue removes "slow" first because it arrived first. In a priority queue where a smaller number is better, "urgent" is removed first because priority 1 is better than priorities 3 and 5.

The difference is the selection rule. A normal queue selects the oldest item. A priority queue selects the current best candidate, even when that candidate arrived later.

The Core Rule

Each entry has an item and a priority. Whenever the next entry is requested, the priority queue selects the entry with the best priority among all entries currently stored.

The word “best” matters more than whether a priority number sounds high or low. A priority queue does not decide what the numbers mean. The algorithm using the queue defines their meaning.

What the Priority Number Means

“Highest priority” does not necessarily mean the largest number. Depending on the problem, the best candidate might have:

• The smallest cost.
• The shortest distance.
• The earliest deadline.
• The greatest urgency.

Python’s heapq removes the smallest value first. The examples in this document therefore use smaller numbers for candidates that should be selected earlier. Priority 1 is better under this ordering than priority 5.

When larger numeric values should be selected first, numeric priorities can often be negated before they are stored. That changes a maximum-selection problem into the minimum-selection order that heapq provides.

Basic Operations

A priority queue supports three basic operations:

• Push adds a candidate and its priority.
• Peek returns the current best candidate without removing it.
• Pop removes and returns the current best candidate.

These operations describe the behavior of the data structure. In Python’s heapq, they correspond to heapq.heappush(pq, entry), pq[0], and heapq.heappop(pq).

Peek requires the queue to be non-empty. Accessing pq[0] when pq is empty raises IndexError.

Step-by-Step Example

Start with an empty priority queue. Smaller numbers represent better priorities.

Step 1: Push Slow

Push (5, "slow"). It is the only candidate, so it is also the next candidate that peek or pop would select.

Candidates: (5, "slow")
Next: (5, "slow")

Step 2: Push Urgent

Push (1, "urgent"). It arrived after "slow", but priority 1 is better than priority 5.

Candidates: (5, "slow"), (1, "urgent")
Next: (1, "urgent")

Step 3: Push Normal

Push (3, "normal"). The best priority is still 1.

Candidates: (5, "slow"), (1, "urgent"), (3, "normal")
Next: (1, "urgent")

The candidate display above is a conceptual set of entries. It is not a picture of Python’s internal heap list and does not claim that the entries are fully sorted.

Step 4: Peek, Then Pop Urgent

Peek returns (1, "urgent") without removing it. The first pop then removes and returns the same entry because it has the smallest priority number.

Remaining candidates: (5, "slow"), (3, "normal")
Next: (3, "normal")

Step 5: Pop Normal

The next pop removes (3, "normal") because priority 3 is now better than priority 5.

Remaining candidate: (5, "slow")
Next: (5, "slow")

Step 6: Pop Slow

The final pop removes (5, "slow"). The priority queue is now empty.

This trace shows that insertion order does not determine removal order. Every peek or pop reevaluates which stored candidate has the best priority.

Priority Queue vs. Heap

A priority queue is an abstract behavior or interface. It promises that candidates can be added and that the current best candidate can be inspected or removed.

A heap is a data structure commonly used to implement that behavior. It maintains enough internal order to provide efficient access to the smallest or largest entry without fully sorting every entry after each change.

Python’s heapq provides a min-heap using a list, and that min-heap can be used to implement a priority queue. The two concepts are related but not identical. The priority queue describes what the operations do. The heap describes how those operations can be implemented efficiently.

Heap explains the tree structure, index relationships, and reordering operations. The important fact here is that the internal list satisfies a heap condition rather than being completely sorted.

Python heapq Example

The conceptual entries from the trace can be stored as (priority, item) tuples:

import heapq
 
 
pq = []
 
heapq.heappush(pq, (5, "slow"))
heapq.heappush(pq, (1, "urgent"))
heapq.heappush(pq, (3, "normal"))
 
while pq:
    priority, item = heapq.heappop(pq)
    print(priority, item)

The output is:

1 urgent
3 normal
5 slow

Python compares tuples from left to right. The first value is therefore the primary comparison key, which makes priority control the removal order in this example. If two priorities tie, Python continues by comparing later tuple values.

The list held in pq should not be read as a fully sorted list. Only the smallest heap entry is guaranteed to be at pq[0]. Use heappop to remove entries in priority order.

How Dijkstra Uses It

Dijkstra’s algorithm repeatedly asks:

Which unfinalized vertex currently has the smallest tentative distance?

The priority queue stores candidates as (distance, node). Popping the current minimum efficiently selects the cheapest candidate for the algorithm to examine next.

The priority queue does not calculate paths, improve distances, or prove that a distance is final. Dijkstra manages those parts. The queue’s role is narrower: select the least-distance candidate among the entries it currently holds. Dijkstra’s Algorithm explains tentative distances, finalization, relaxation, and why this selection is safe with non-negative edges.

Advanced Python Details

The basic push, peek, and pop behavior is enough for many uses. The following patterns solve additional problems that arise in some Python programs.

Tie-Breaking

Python compares tuples from left to right. If two entries have the same priority, it compares the next values. That can fail when the stored items do not support comparison with each other.

A numeric counter provides a safe, unique second comparison key:

counter = 0
heapq.heappush(pq, (priority, counter, item))
counter += 1

Entries are then compared by priority first and counter second. Python does not need to compare item values when both earlier fields differ.

Stale Entries

heapq does not directly change the priority of an entry already stored in the heap. When an algorithm discovers a better priority for the same logical item, a common approach is to push a new entry and leave the old one in place.

The old entry is stale. When it is later popped, the algorithm compares its priority with the current best value stored elsewhere and skips it when the values differ:

while pq:
    priority, node = heapq.heappop(pq)
 
    if priority != best_priority[node]:
        continue
 
    # Process the current entry.

This pattern appears in Dijkstra implementations. Heap entries are candidates, and the stale-entry check determines whether a popped candidate is still current. See the Dijkstra document for the full algorithmic reason.

Complexity

For a heap containing n entries:

• Push takes O(log n) time.
• Peek takes O(1) time.
• Pop takes O(log n) time.
• Storing n entries takes O(n) space.

These bounds make a heap useful when candidates are repeatedly added and the current best one is repeatedly removed. They do not mean that every heap operation is fast. Searching for an arbitrary item is still O(n), and the heap’s internal list is not fully sorted.

Algorithms that leave stale entries in the heap may temporarily store more heap entries than there are logical items.

Common Confusions

A priority queue is not the same as a normal queue. FIFO order answers “Which item arrived first?” Priority order answers “Which stored candidate is best now?”

A priority queue is also not the same concept as a heap. A heap is one common implementation of priority-queue behavior.

The internal heap list is not a sorted list. The heap guarantees access to the current minimum, not sorted positions for every entry.

Finally, a smaller number is not universally a better priority. It is the convention used by these examples because Python’s heapq is a min-heap.

When to Use It

Use a priority queue when a changing candidate set must repeatedly answer, “Which candidate is currently best?” Common priority meanings include cost, distance, deadline, urgency, and score.

If removal must follow arrival order, use a normal queue. If all values only need to be sorted once after collection, a regular sort may be simpler.

The Main Point

A priority queue selects the current best candidate rather than the oldest candidate. Push changes the candidate set, peek inspects the best candidate, and pop removes it. A heap is a common way to implement these operations efficiently, while the algorithm using the queue defines what “best” means.