Source: Comprehensive Guide to Tries, Heaps, and Priority Queues – UCF Computer Science I
Difficulty: Intermediate | Prerequisites: Heaps (see Heaps study notes), basic abstract data types.
Tags: priority queue, min-priority queue, max-priority queue, abstract data type, insert, extract min, extract max, decrease key, increase key, Dijkstra's algorithm, scheduling, event simulation
Priority queues appear once you have heaps under your belt, because a priority queue is the abstract idea and a heap is the concrete implementation. Where a regular queue is first-in-first-out, a priority queue serves the highest-priority (or lowest-priority) element next, regardless of arrival order. This abstraction powers a wide range of algorithms: Dijkstra's shortest path, Prim's minimum spanning tree, CPU scheduling, and event-driven simulation. The course introduces them here so you can see how a clean abstract interface maps onto the efficient heap operations you have already learnt.
A priority queue is an abstract data type that lets you insert elements with priorities and always retrieve the one with the highest (or lowest) priority first. Under the hood it is typically a heap, giving O(log n) insert and extract and O(1) peek at the extreme element.
Priority queue
An abstract data type where each element has an associated priority and the element with the highest (or lowest) priority can be retrieved efficiently. Think of it as a hospital A&E waiting room: the most urgent patient is seen next, not the one who arrived first.
Max-priority queue
A priority queue variant where the element with the largest key is served first. Supports Insert, Maximum, Extract-Maximum, and Increase-Key.
Min-priority queue
A priority queue variant where the element with the smallest key is served first. Supports Insert, Minimum, Extract-Minimum, and Decrease-Key.
Extract-Maximum / Extract-Minimum
Removes and returns the element with the highest (or lowest) priority. This is the core "serve the next most important item" operation.
Decrease-Key / Increase-Key
Changes the priority of an element already in the queue. Decrease-Key lowers a key (used in min-priority queues, e.g. when Dijkstra's finds a shorter path). Increase-Key raises a key (used in max-priority queues). In simple terms, this is how you update an item's urgency after it has already been added.
Insert(Q, k): Add an element with key k to the queue. Internally, this appends to the heap array and bubbles up.
Maximum(Q): Return (but do not remove) the element with the largest key. This is just a peek at the root of a max-heap – O(1).
Extract-Maximum(Q): Remove and return the element with the largest key. Replaces the root with the last element and heapifies down – O(log n).
Increase-Key(Q, x, k): Set element x's key to a new, larger value k, then bubble up to restore the heap – O(log n).
Insert(Q, k): Same idea as the max variant, but using a min-heap underneath.
Minimum(Q): Peek at the root – O(1).
Extract-Minimum(Q): Remove the root, replace with the last element, heapify down – O(log n).
Decrease-Key(Q, x, k): Lower element x's key to k, then bubble up – O(log n).
Peek (Maximum or Minimum): O(1). The extreme element is always at the root of the underlying heap.
Insert: O(log n). One bubble-up pass through at most log n levels.
Extract: O(log n). One heapify-down pass.
Decrease-Key / Increase-Key: O(log n). One bubble-up pass.
A sorted array gives O(1) access to the extreme element and O(1) removal from the end, but insertion requires O(n) to shift elements and maintain sorted order.
A heap gives O(log n) for both insert and extract, which is a better trade-off when you have a mix of inserts and extractions, as most real workloads do.
Operation | Time | Backed by |
|---|---|---|
Peek (min or max) | O(1) | Read root |
Insert | O(log n) | Bubble up |
Extract min / max | O(log n) | Replace root + heapify |
Decrease / increase key | O(log n) | Bubble up |
Dijkstra's shortest-path algorithm uses a min-priority queue to always process the closest unvisited vertex next. Without the priority queue, you would scan all vertices each round, turning an O((V + E) log V) algorithm into O(V²).
Operating system task schedulers use max-priority queues to run the highest-priority process. When a process's priority changes (e.g. it has been waiting too long), the scheduler calls Increase-Key.
Students often treat "priority queue" and "heap" as the same thing. They are not. A priority queue is the abstract interface (what operations are available). A heap is one possible implementation (how those operations are carried out). You could implement a priority queue with a sorted list, an unsorted list, or a balanced BST, though a heap is the most common choice.
Confusing which variant to use: Dijkstra's needs a min-priority queue (you want the nearest node), while a job scheduler wanting to serve the most important job first needs a max-priority queue.
Assuming Decrease-Key and Increase-Key are interchangeable. Decrease-Key only makes sense in a min-priority queue (lowering a key might move it upward). Increase-Key only makes sense in a max-priority queue (raising a key might move it upward). Using the wrong one violates the heap property in the wrong direction.
⚠️ You may be asked to name the four standard operations of each variant (max and min). Memorise them.
⚠️ Exam questions commonly ask: "What data structure would you use to efficiently get the smallest element from a dynamic collection?" The answer is a min-priority queue, backed by a min-heap.
⚠️ Expect a question linking priority queues to a specific algorithm (Dijkstra's, Prim's, or heapsort) and asking you to explain which variant is used and why.
⚠️ Know the O(1) vs O(log n) distinction: peeking is O(1), but extracting is O(log n) because of the repair step.
True or false: A priority queue is a concrete data structure, not an abstract data type.
Fill in the blank: In a min-priority queue backed by a min-heap, the element returned by Minimum(Q) is at index ______ of the underlying array.
True or false: Decrease-Key is typically used in a max-priority queue.
Fill in the blank: Insert into a priority queue backed by a heap runs in ______ time.
True or false: Dijkstra's shortest-path algorithm uses a max-priority queue.
Answers: 1. False (it is an abstract data type). 2. 0 (the root). 3. False (used in a min-priority queue). 4. O(log n). 5. False (it uses a min-priority queue).
Q: A max-priority queue contains elements with keys [15, 10, 12, 5, 8]. You call Insert(Q, 20). Describe what happens internally.
A: The heap array becomes [15, 10, 12, 5, 8, 20]. The new element (20) at index 5 compares with its parent at index 2 (value 12). 20 > 12, so they swap → [15, 10, 20, 5, 8, 12]. Now 20 at index 2 compares with the root at index 0 (value 15). 20 > 15, swap → [20, 10, 15, 5, 8, 12]. 20 is now the root and the heap property is restored.
Q: Why is a sorted array a poor backing structure for a priority queue with frequent inserts?
A: Each insert into a sorted array requires finding the correct position (O(log n) with binary search) and then shifting all subsequent elements to make room (O(n)). A heap achieves insert in O(log n) with no shifting, because it only needs to bubble up through a tree of height log n.
Q: Name an algorithm that uses a min-priority queue and explain what role the queue plays.
A: Dijkstra's shortest-path algorithm maintains a min-priority queue of vertices keyed by their current shortest known distance from the source. At each step it extracts the vertex with the smallest distance, relaxes its edges, and calls Decrease-Key on any neighbour whose distance improves. The queue ensures you always process the closest vertex next, which is what makes the algorithm correct and efficient.
Priority queues depend on heaps, so understanding heap operations (insert, heapify, extract) is a prerequisite for everything here. If the heap notes are not solid yet, revisit those first.
Priority queues connect forward to graph algorithms. Dijkstra's and Prim's both rely on efficiently extracting the minimum-key vertex, which is the min-priority queue's core job. When you study those algorithms, the priority queue is the piece that determines the overall time complexity.
priority queue, min-priority queue, max-priority queue, abstract data type, ADT, heap-backed priority queue, insert priority queue, extract min, extract max, decrease key, increase key, Dijkstra's algorithm priority queue, Prim's algorithm priority queue, job scheduling priority queue, event-driven simulation, priority queue vs heap, priority queue vs sorted array, CS 101 UCF priority queues