Priority Queue | Engineering Interview Kit

Concept

In computer science, a Heap and a Priority Queue are practically synonymous, but technically:

A Heap is the physical underlying data structure (the Array with the Complete Tree math).
A Priority Queue (PQ) is the abstract data type (the API) that sits on top of the Heap.

In a standard Queue (FIFO), you are served in the exact order you arrived.
In a Priority Queue, every item has a “Priority Score”. When you call dequeue(), the PQ ignores arrival time and instantly returns the item with the absolute highest priority.

Real-World Mental Model

Think of a Hospital Emergency Room.

Patient A arrives with a sprained ankle. (Priority: Low)
Patient B arrives an hour later with a heart attack. (Priority: High)
When the doctor becomes available, they do not treat Patient A first. The Triage Nurse (the Priority Queue) instantly routes Patient B to the doctor, completely bypassing the line.

Implementation Details

Instead of a Min-Heap just storing raw numbers like [5, 10, 2], a Priority Queue usually stores Objects or Tuples: { value: "Patient B", priority: 1 }.

The bubbleUp and bubbleDown algorithms inside the Heap simply compare the priority property of the objects instead of the values themselves.

// Conceptual Priority Queue API
const pq = new MinPriorityQueue();

pq.enqueue("Patient A", 5); // Sprained ankle
pq.enqueue("Patient B", 1); // Heart attack
pq.enqueue("Patient C", 3); // Broken arm

console.log(pq.dequeue().value); // Instantly outputs: "Patient B"
console.log(pq.dequeue().value); // Instantly outputs: "Patient C"

Graph Algorithms (Dijkstra’s)

The single most important application of a Priority Queue in advanced algorithms is Dijkstra’s Shortest Path Algorithm.

When searching for the shortest path on a map from City A to City Z, a standard Breadth-First Search (using a normal Queue) assumes every road takes 1 hour to drive.
But what if the road to City B takes 10 hours, and the road to City C takes 2 hours?

Dijkstra’s Algorithm uses a Min-Priority Queue.
As it explores the map, it pushes every newly discovered city into the PQ, using the total driving time from the start as the Priority Score.
Because the PQ always pops the city with the lowest score, Dijkstra mathematically guarantees that it is always exploring the absolute shortest physical paths first!

Interview Questions

Q: A developer needs a Priority Queue in JavaScript. They decide to just push objects into a standard Array, and every time they need to dequeue, they run array.sort((a,b) => a.priority - b.priority) and .shift() the first item. Why will this fail an interview?
A: Calling .sort() takes $O(N \log N)$ time. Calling .shift() takes $O(N)$ time.
If there are 10,000 items in the queue, dequeuing a single item will take massive amounts of CPU power.
A true Heap-based Priority Queue guarantees that finding the highest priority item takes $O(1)$ time, and extracting it takes strictly $O(\log N)$ time.

Q: What happens in a Priority Queue if two items have the exact same priority score?
A: In a pure Heap implementation, the tie-breaking behavior is technically undefined (it depends on exactly how the bubble algorithms swap elements).
If strict FIFO order must be maintained for items with identical priorities (like in an Operating System task scheduler), the Priority Queue objects must include a secondary timestamp property: { task: "A", priority: 1, timestamp: 12345 }. The bubbleUp logic is modified: if (a.priority === b.priority) return a.timestamp - b.timestamp;.