What is a Priority Queue?
Learn what a priority queue is, how binary heaps give O(log n) insert/extract, and where it powers Dijkstra, with Python code examples.
Expected Interview Answer
A priority queue is an abstract data type where each element has a priority, and the element with the highest (or lowest) priority is always removed first, typically implemented with a binary heap for O(log n) insert and extract.
Unlike a regular queue that is strictly first-in-first-out, a priority queue reorders based on priority value rather than arrival order. Binary heaps are the standard implementation because they give O(log n) insertion and O(log n) extraction of the min or max, plus O(1) peek at the top element, all using an array-backed complete binary tree with no pointer overhead. Priority queues power algorithms like Dijkstra’s shortest path, Huffman coding, and task schedulers that must always process the most urgent item next.
- O(log n) insert and extract-min/max
- O(1) peek at the highest-priority element
- Array-backed heap needs no extra pointers
- Core building block for Dijkstra and A* search
AI Mentor Explanation
A priority queue is like a hospital tent at a cricket ground where the physio treats the most severely injured player next, not whoever limped in first. A player with a suspected fracture jumps ahead of one with a minor cramp, regardless of arrival order. Internally, the tent staff keep the most urgent case at the front by re-sorting whenever a new patient arrives or the top case is treated, which is exactly how a heap-backed priority queue reorders on insert and extract.
Step-by-Step Explanation
Step 1
Choose the priority ordering
Decide whether smaller or larger priority values are extracted first (min-heap or max-heap).
Step 2
Insert maintains heap property
Add the element at the end and sift it up until parent-child ordering holds.
Step 3
Extract removes the root
Swap the root with the last element, remove it, then sift the new root down.
Step 4
Use for priority-driven algorithms
Apply it in Dijkstra, A*, Huffman coding, and event schedulers.
What Interviewer Expects
- Distinction between priority queue and FIFO queue
- Correct O(log n) insert/extract complexity via a heap
- Awareness of min-heap versus max-heap use cases
- Ability to name at least one real algorithm that uses it
Common Mistakes
- Confusing a priority queue with a sorted array (which has O(n) insert)
- Assuming a priority queue is FIFO for equal priorities without checking
- Forgetting extract-min/max is O(log n), not O(1)
- Not knowing peek is O(1) while extraction is O(log n)
Best Answer (HR Friendly)
“A priority queue is a to-do list that always serves the most urgent item first, not the item that was added first, which is why it’s used anywhere the next task to run depends on importance rather than arrival order, like hospital triage or task schedulers.”
Code Example
import heapq
pq = []
heapq.heappush(pq, (2, "check disk space"))
heapq.heappush(pq, (1, "server down"))
heapq.heappush(pq, (3, "update docs"))
while pq:
priority, task = heapq.heappop(pq)
print(priority, task)Follow-up Questions
- How would you implement a max-heap using Python’s heapq, which is min-heap only?
- How does a priority queue power Dijkstra’s algorithm?
- What is the time complexity of building a heap from an unsorted array?
- How do you handle equal-priority elements fairly (tie-breaking)?
MCQ Practice
1. What is the time complexity of inserting an element into a heap-backed priority queue?
Insertion sifts the new element up the heap, taking O(log n) in the worst case.
2. What is the time complexity of peeking at the highest-priority element without removing it?
The highest-priority element sits at the heap’s root, so peek is constant time.
3. Which algorithm relies on a priority queue to always expand the closest unvisited node next?
Dijkstra’s algorithm uses a priority queue to always process the nearest unvisited node.
Flash Cards
Priority queue? — An ADT where the highest (or lowest) priority element is always removed first.
Typical implementation? — A binary heap, giving O(log n) insert/extract and O(1) peek.
Versus FIFO queue? — A regular queue orders by arrival time; a priority queue orders by priority value.
Common use case? — Dijkstra’s shortest path, task schedulers, Huffman coding.