Priority Queue with Custom Comparator

A PriorityQueue wraps a min-heap and accepts a comparator so you can enqueue arbitrary objects and always dequeue the highest-priority one in O(log n).

5 min read Level 3/5 #dsa#heap#priority-queue

What you'll learn

Build a PriorityQueue class with enqueue, dequeue, peek, and size
Use a comparator to order objects by a custom field
Trace how Dijkstra's algorithm relies on a priority queue

A priority queue is an abstract data type that always returns the element with the highest priority. Implemented on a min-heap with a comparator, it handles any value type — numbers, objects, tuples — in O(log n) per operation.

PriorityQueue Class

The comparator follows the same convention as Array.prototype.sort: negative means a has higher priority, zero means equal, positive means b has higher priority.

class PriorityQueue {
  #data = [];
  #cmp;

  // Default comparator: numeric min-heap
  constructor(cmp = (a, b) => a - b) {
    this.#cmp = cmp;
  }

  get size() { return this.#data.length; }
  isEmpty()  { return this.#data.length === 0; }
  peek()     { return this.#data[0]; }

  enqueue(val) {
    this.#data.push(val);
    this.#siftUp(this.#data.length - 1);
  }

  dequeue() {
    const d = this.#data;
    if (!d.length) return undefined;
    const top = d[0];
    const last = d.pop();
    if (d.length) { d[0] = last; this.#siftDown(0); }
    return top;
  }

  #siftUp(i) {
    const d = this.#data;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.#cmp(d[p], d[i]) <= 0) break;
      [d[p], d[i]] = [d[i], d[p]];
      i = p;
    }
  }

  #siftDown(i) {
    const d = this.#data;
    const n = d.length;
    while (true) {
      let best = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < n && this.#cmp(d[l], d[best]) < 0) best = l;
      if (r < n && this.#cmp(d[r], d[best]) < 0) best = r;
      if (best === i) break;
      [d[best], d[i]] = [d[i], d[best]];
      i = best;
    }
  }
}

Ordering Objects by a Field

Pass a custom comparator to sort by any property:

// Min-heap by task priority (lower number = higher priority)
const taskQueue = new PriorityQueue((a, b) => a.priority - b.priority);

taskQueue.enqueue({ name: 'send email',   priority: 3 });
taskQueue.enqueue({ name: 'fix crash',    priority: 1 });
taskQueue.enqueue({ name: 'write tests',  priority: 2 });

console.log(taskQueue.dequeue().name); // 'fix crash'    (priority 1)
console.log(taskQueue.dequeue().name); // 'write tests'  (priority 2)

Dijkstra’s Algorithm Sketch

Dijkstra repeatedly extracts the unvisited node with the smallest tentative distance — exactly what a priority queue provides:

function dijkstra(graph, source) {
  const dist = {};
  const pq = new PriorityQueue((a, b) => a.dist - b.dist);

  for (const node of Object.keys(graph)) dist[node] = Infinity;
  dist[source] = 0;
  pq.enqueue({ node: source, dist: 0 });

  while (!pq.isEmpty()) {
    const { node, dist: d } = pq.dequeue();
    if (d > dist[node]) continue;         // stale entry, skip

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

API Summary

Method	Time	Description
enqueue(val)	O(log n)	Add a value
dequeue()	O(log n)	Remove and return highest priority
peek()	O(1)	Read highest priority without removing
size	O(1)	Number of elements

Up Next

Apply the priority queue to the classic top-k problem: efficiently finding the k largest or most frequent elements from a stream.

Top-K Elements with a Size-K Heap →