A priority queue is an abstract data structure where each element has an associated priority value. Unlike a standard queue — where elements leave in the order they arrived — a priority queue always removes the highest-priority element first, regardless of when it was added.
How does a priority queue differ from a regular queue?
A regular queue follows FIFO (First In, First Out): the first item added is the first removed. Think of a queue at a cinema: whoever joined first buys their ticket first, no exceptions.
A priority queue follows a different rule: highest priority out first. Think of an emergency department. A patient who arrives with a minor sprain waits even if they arrived before a patient arriving later with a suspected heart attack. The heart attack patient has a higher clinical priority and is seen first.
| Feature | Queue (FIFO) | Priority queue |
|---|---|---|
| Order of removal | Arrival order | Priority value |
| Real-world model | Post office queue | A&E triage |
| Operations | Enqueue, Dequeue | Enqueue (with priority), Dequeue |
| Underlying structure | Array or linked list | Heap (usually) |
What operations does a priority queue support?
Like all abstract data types, a priority queue is defined by its operations:
- Enqueue(item, priority) — add an item with its associated priority. If two items have the same priority, they are usually served in arrival order (first-come, first-served as a tiebreaker).
- Dequeue() — remove and return the item with the highest priority. This is sometimes called extract-max (for a max-priority queue) or extract-min (for a min-priority queue, where lower numbers mean higher priority — e.g. priority 1 is more urgent than priority 5).
- Peek() — inspect the highest-priority item without removing it.
- IsEmpty() — return True if the queue contains no items.
How do you trace a priority queue by hand?
Worked example — a hospital triage queue (lower number = higher priority):
| Step | Action | Queue state (priority: name) |
|---|---|---|
| 1 | Enqueue(Aisha, 3) | [(3, Aisha)] |
| 2 | Enqueue(Marcus, 1) | [(1, Marcus), (3, Aisha)] |
| 3 | Enqueue(Priya, 2) | [(1, Marcus), (2, Priya), (3, Aisha)] |
| 4 | Dequeue() → returns Marcus | [(2, Priya), (3, Aisha)] |
| 5 | Enqueue(Leon, 1) | [(1, Leon), (2, Priya), (3, Aisha)] |
| 6 | Dequeue() → returns Leon | [(2, Priya), (3, Aisha)] |
Notice that Leon was enqueued after Priya and Aisha, but his priority of 1 means he is served before them.
How is a priority queue implemented efficiently?
The most efficient implementation uses a binary heap — a tree-based data structure that maintains the property that every parent node has a higher (or equal) priority than its children.
Min-heap property: the root node always holds the minimum (highest-priority) value.
A heap can be stored in a flat array using index arithmetic (no pointers needed):
- Parent of node at index i:
(i - 1) // 2 - Left child of node at index i:
2i + 1 - Right child of node at index i:
2i + 2
Performance:
| Operation | Time complexity |
|---|---|
| Enqueue | O(log n) — item may bubble up through the heap |
| Dequeue | O(log n) — root removed and heap rebalanced |
| Peek | O(1) — root is always accessible |
By comparison, a simple unsorted array implementation gives O(1) enqueue but O(n) dequeue (must scan all items to find the minimum). A heap is the standard choice for real applications.
Where are priority queues used in real systems?
Priority queues are a fundamental building block of many algorithms and systems:
- Operating system process scheduling — processes are assigned priorities; the CPU always runs the highest-priority ready process next
- Dijkstra's shortest path algorithm — nodes are explored in priority order of distance, requiring a min-priority queue
- Network packet routing — routers process packets labelled with Quality of Service (QoS) priority, ensuring voice calls are not delayed by background file downloads
- Print queues — documents marked as urgent may be processed before documents that arrived earlier
- Event simulation — events are processed in order of their scheduled time (a form of priority based on timestamp)
- A* pathfinding — used in games and navigation, explores nodes in priority order of estimated cost
Frequently asked questions
How is a priority queue different from a sorted list?
A sorted list keeps all elements in order at all times. Inserting into a sorted list costs O(n) because you must find the correct position and shift elements. A priority queue (heap) costs O(log n) for both insertion and extraction. If you need to dequeue the highest-priority item repeatedly but do not need all items sorted all the time, a priority queue is more efficient.
Do I need to know how the heap works internally for GCSE?
At GCSE level, you are expected to understand the abstract behaviour of a priority queue — what it does, how it differs from a regular queue, and real-world applications. The internal heap implementation is more commonly assessed at A-level. Check your specific exam board's specification for exact requirements, but being able to trace priority queue operations by hand (as in the example above) is the typical GCSE expectation.
Is Python's queue.PriorityQueue a min-queue or a max-queue?
Python's built-in queue.PriorityQueue and heapq module both implement a min-heap — the element with the lowest numerical priority value is dequeued first. To simulate a max-priority queue (where higher numbers mean higher priority), store priorities as negative numbers: enqueue priority 5 as -5, and the item stored at -5 will be dequeued first because -5 < -3 < -1.
Can a priority queue have duplicate priorities?
Yes. When multiple items share the same priority, most implementations return them in arrival order (FIFO as a secondary rule), though this depends on the specific implementation. Python's heapq breaks ties by comparing the items themselves, so storing items as (priority, arrival_order, data) tuples is a common pattern to enforce FIFO among equal priorities.
Want to master abstract data types for your GCSE? Professor Turing at aitutors.me will trace every data structure operation with you until it is second nature.