Priority Queue

Explanation

A priority queue is an abstract data type with three operations: insert (add an element with a priority), extractMax/extractMin (remove and return the highest/lowest priority element), and peek (view the highest/lowest priority without removing it). The "queue" name is a misnomer — it's not FIFO. Items leave based on priority, not arrival order. The canonical implementation is a binary heap: a min-heap for a min-priority queue and a max-heap for a max-priority queue. This gives O(log n) insert and extract, and O(1) peek. For n items, building the initial heap from an array is O(n) — more efficient than inserting one by one (O(n log n)). Real-world applications: Dijkstra's shortest-path algorithm processes the unvisited node with the smallest known distance next — a min-priority queue keyed by distance. A* search uses a priority queue ordered by f = g + h (actual cost + heuristic estimate). OS process schedulers give CPU time to the highest-priority process. Network routers prioritize certain types of packets. Bandwidth throttling systems serve requests in priority order. In job queues (Bull, Celery, Sidekiq), priority queues ensure that "urgent" jobs run before "low" jobs even if the low-priority jobs arrived first. This is a pattern you'll encounter in production systems far more than in typical coding exercises.

Code Example

// Priority queue backed by a min-heap
// (using the MinHeap from the Heap glossary entry)

// Dijkstra's core pattern using a priority queue
function dijkstra(graph, start) {
  const dist = new Map();
  const pq = new MinHeap(); // [{dist, node}] ordered by dist

  for (const node of graph.keys()) dist.set(node, Infinity);
  dist.set(start, 0);
  pq.push({ dist: 0, node: start });

  while (pq.size() > 0) {
    const { dist: d, node } = pq.pop();
    if (d > dist.get(node)) continue; // outdated entry

    for (const [neighbor, weight] of graph.get(node)) {
      const newDist = d + weight;
      if (newDist < dist.get(neighbor)) {
        dist.set(neighbor, newDist);
        pq.push({ dist: newDist, node: neighbor });
      }
    }
  }
  return dist;
}

Why It Matters for Engineers

Priority queues are the data structure behind shortest-path algorithms (Dijkstra, A*), which underpin GPS navigation, game AI pathfinding, network routing, and social network suggestions ("people you may know" traverses a weighted graph). Understanding priority queues lets you implement and reason about these algorithms. In system design interviews and real architecture decisions, priority queues also appear as the solution to "how do you handle urgent requests when the system is under load?" — a question about designing fair, priority-aware systems. Knowing the data structure and its performance characteristics gives you a concrete answer.