Priority Queue

How a priority queue works

A regular queue is FIFO — first in, first out. A priority queue ignores arrival order and pops whichever item has the smallest (or largest) key. Think of a hospital triage room: patients aren't seen in the order they walked through the door, they're seen by severity.

The interface is small:

• push(item, priority) — insert an element.
• pop() — remove and return the highest-priority element.
• peek() — return the highest-priority element without removing it.

The catch is making both push and pop fast. A sorted array gives O(1) pop but O(n) push. An unsorted array gives O(1) push but O(n) pop. Neither is good enough for graph algorithms that do millions of priority operations. The binary heap balances them at O(log n) each, which is what every standard library actually ships.

The binary heap, in a single array

A binary heap is a complete binary tree that satisfies the heap property: every parent is smaller (min-heap) or larger (max-heap) than its children. Because the tree is complete — filled level by level, left to right — you don't need pointers. Just store it in an array:

index:    0   1   2   3   4   5   6
value:    1   3   2   7   8   4   5

         1                 ← root (index 0)
        / \
       3   2               ← index 1, 2
      / \ / \
      7 8 4 5              ← index 3, 4, 5, 6

Parent of i is at (i - 1) / 2. Left child is at 2i + 1, right child at 2i + 2. No memory allocator, no pointer-chasing — just integer arithmetic on a flat array. This cache-friendliness is why binary heaps beat fancier heap variants on real hardware.

Push adds the new value at the end of the array, then sifts up: while it's smaller than its parent, swap with the parent. Pop returns arr[0], moves the last element to arr[0], then sifts down: while it's larger than its smaller child, swap with that child. Both walk at most log₂ n levels.

When to use a priority queue

• Graph search — Dijkstra and A* repeatedly extract the cheapest unvisited frontier node.
• Scheduling — OS run queues, event simulators, expiring TTL caches.
• Top-K selection — keep the K largest or smallest items from a stream without sorting everything.
• Median maintenance — two heaps (min + max) split around the running median.
• Huffman coding — repeatedly merge the two least-frequent symbols.

Priority queue implementations compared

	Binary heap	Sorted array	Unsorted array	Balanced BST	Pairing heap	Fibonacci heap
Push	O(log n)	O(n)	O(1)	O(log n)	O(1)	O(1)
Pop min	O(log n)	O(1)	O(n)	O(log n)	O(log n) amort.	O(log n) amort.
Peek	O(1)	O(1)	O(n)	O(log n)	O(1)	O(1)
Decrease-key	O(log n)	O(n)	O(1)	O(log n)	O(log n) amort.	O(1) amort.
Merge two heaps	O(n)	O(n)	O(1)	O(n)	O(1)	O(1)
Cache friendliness	Excellent (flat array)	Excellent	Excellent	Poor (pointers)	Poor	Very poor
Real-world winner for	Dijkstra, top-K, defaults	Tiny, mostly-static sets	Insert-heavy with batched pops	Need ordered iteration too	Decrease-key bottleneck	Theoretical lower bounds

The honest takeaway: unless profiling tells you otherwise, use the binary heap. Pairing and Fibonacci heaps look better on paper but lose to the flat-array binary heap on every modern cache, and the asymptotic decrease-key advantage rarely materializes in real graphs.

Pseudo-code (min-heap)

function push(heap, x):
    heap.append(x)
    siftUp(heap, heap.length - 1)

function pop(heap):
    top = heap[0]
    last = heap.pop()
    if heap not empty:
        heap[0] = last
        siftDown(heap, 0)
    return top

function siftUp(heap, i):
    while i > 0:
        parent = (i - 1) / 2
        if heap[i] >= heap[parent]: break
        swap(heap, i, parent)
        i = parent

function siftDown(heap, i):
    n = heap.length
    while 2i + 1 < n:
        smallest = 2i + 1
        if 2i + 2 < n and heap[2i + 2] < heap[smallest]:
            smallest = 2i + 2
        if heap[i] <= heap[smallest]: break
        swap(heap, i, smallest)
        i = smallest

JavaScript implementation

class MinHeap {
  constructor() { this.h = []; }
  size() { return this.h.length; }
  peek() { return this.h[0]; }

  push(x) {
    this.h.push(x);
    this._siftUp(this.h.length - 1);
  }

  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) { this.h[0] = last; this._siftDown(0); }
    return top;
  }

  _siftUp(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[i] >= this.h[p]) break;
      [this.h[i], this.h[p]] = [this.h[p], this.h[i]];
      i = p;
    }
  }

  _siftDown(i) {
    const n = this.h.length;
    while (true) {
      const l = 2 * i + 1, r = 2 * i + 2;
      let s = i;
      if (l < n && this.h[l] < this.h[s]) s = l;
      if (r < n && this.h[r] < this.h[s]) s = r;
      if (s === i) break;
      [this.h[i], this.h[s]] = [this.h[s], this.h[i]];
      i = s;
    }
  }
}

// Top-K largest using a size-K min-heap.
function topK(items, k) {
  const h = new MinHeap();
  for (const x of items) {
    if (h.size() < k) h.push(x);
    else if (x > h.peek()) { h.pop(); h.push(x); }
  }
  return h.h.sort((a, b) => b - a);
}

JavaScript has no built-in priority queue, which is why every interview LeetCode answer ships its own. Node 22 finally added BinaryHeap behind a flag, but most production code still uses a hand-rolled class or a library like @datastructures-js/priority-queue.

Python implementation

import heapq

# Dijkstra's shortest path using heapq
def dijkstra(graph, start):
    dist = {start: 0}
    pq = [(0, start)]                    # (distance, node)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')):  # stale entry, skip
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

# A* with tiebreak on insertion order to keep behaviour deterministic
import itertools
def astar(start, goal, neighbors, h):
    counter = itertools.count()
    pq = [(h(start), 0, next(counter), start, [start])]
    seen = {}
    while pq:
        f, g, _, node, path = heapq.heappop(pq)
        if node == goal: return path
        if g > seen.get(node, float('inf')): continue
        seen[node] = g
        for nb, w in neighbors(node):
            ng = g + w
            if ng < seen.get(nb, float('inf')):
                heapq.heappush(pq, (ng + h(nb), ng, next(counter), nb, path + [nb]))
    return None

Two real-world details matter here. First, both Dijkstra and A* allow stale entries in the heap rather than implementing decrease-key — the if d > dist[u]: continue check throws them away on pop. Second, A* needs a tiebreaker when two nodes have the same f-score; a monotonic counter keeps the heap from comparing the actual node objects (which may not be orderable).

What the numbers actually look like

• Build-heap is O(n), not O(n log n). A naive sequence of pushes is O(n log n), but you can heapify an existing array bottom-up in O(n). That's why Python's heapq.heapify is the right tool when you have all the data up front.
• Top-K is O(n log K), not O(n log n). For finding the 100 largest in a billion items, that's 100× faster than sorting.
• Dijkstra with binary heap is O((V + E) log V). With Fibonacci heap it's O(E + V log V) — a paper-level improvement that almost nobody cashes in.
• Median of a stream in O(log n). Two heaps (max-heap of lower half, min-heap of upper half) keep the median at the root of one of them.

Variants you'll meet in the wild

d-ary heap. Generalises binary to a tree with d children per node. Higher d makes sift-up cheaper (shallower tree) but sift-down more expensive (more children to compare). Used by Boost C++ and some Dijkstra implementations with d ≈ 4.

Pairing heap. Stores trees of arbitrary shape and merges lazily. Practically fast and simple to implement; what Boost uses for its fibonacci_heap alternative because pairing heap usually wins benchmarks.

Fibonacci heap. Optimal asymptotic decrease-key for theoretical Dijkstra and Prim's. In practice the cascading cuts and bookkeeping make it slower than a binary heap unless graphs are huge and dense.

Leftist heap and skew heap. Pointer-based, support O(log n) merge. Useful in functional languages where in-place updates aren't natural.

Indexed priority queue. A binary heap with a side map from item → index, so decrease-key is true O(log n). Used in some Dijkstra implementations and Prim's where decrease-key happens often.

Bucket queue / monotone priority queue. When priorities are small integers, an array of buckets gives O(1) push and O(C) pop where C is the priority range. Linux's CFS and event-driven simulators use bucket queues.

Common bugs and edge cases

• Pushing comparable tuples with non-comparable items. heappush(pq, (priority, item)) falls back to comparing items if priorities tie, which crashes on dicts/objects. Always include a unique tiebreaker: (priority, counter, item).
• Forgetting min vs max. Python's heapq is min-only; negate priorities or use a wrapper class to invert comparisons for a max-heap.
• Decrease-key without an index map. If you mutate an item already in the heap, the heap property silently breaks. Either use stale-entry-skipping (Dijkstra-style) or maintain an index.
• Iterating over a heap expecting sorted order. The array isn't sorted — only the root is guaranteed minimal. To get sorted output, call pop n times.
• Using a heap where you wanted a stable queue. Two equal-priority items pop in arbitrary order. If insertion order matters as a tiebreaker, encode it explicitly.
• Building a heap by repeatedly pushing. O(n log n) when O(n) is available — call heapify on the whole array instead.