jsschools

Priority Queue

An abstract data type where each element has a priority, and the element with the highest (or lowest) priority is always dequeued first.

Spec ↗

Syntax

class PriorityQueue {
  constructor(compareFn = (a, b) => a[0] - b[0]) { /* heap-based */ }
  enqueue(item) { ... }   // O(log n)
  dequeue()     { ... }   // O(log n) — returns highest-priority item
  peek()        { ... }   // O(1)
}

Parameters

NameTypeRequiredDescription
compareFn (a, b) => number No Comparator that returns negative if a should be dequeued before b. Defaults to min-priority (smallest value first).

Returns

PriorityQueue — A new PriorityQueue instance backed by a binary heap.

Examples

// Min-priority queue — smallest priority first
class PQ {
  #h = [];
  enqueue(val, pri) { this.#h.push([pri, val]); this.#up(this.#h.length - 1); }
  dequeue() {
    const top = this.#h[0];
    const last = this.#h.pop();
    if (this.#h.length) { this.#h[0] = last; this.#down(0); }
    return top;
  }
  peek() { return this.#h[0]; }
  get size() { return this.#h.length; }
  #up(i) { while (i > 0) { const p = (i-1)>>1; if (this.#h[p][0] <= this.#h[i][0]) break; [this.#h[i],this.#h[p]]=[this.#h[p],this.#h[i]]; i=p; } }
  #down(i) { const n=this.#h.length; while(true){ let s=i,l=2*i+1,r=2*i+2; if(l<n&&this.#h[l][0]<this.#h[s][0])s=l; if(r<n&&this.#h[r][0]<this.#h[s][0])s=r; if(s===i)break; [this.#h[i],this.#h[s]]=[this.#h[s],this.#h[i]]; i=s; } }
}

const pq = new PQ();
pq.enqueue('low task',    10);
pq.enqueue('urgent task',  1);
pq.enqueue('medium task',  5);
console.log(pq.dequeue()[1]);
console.log(pq.dequeue()[1]);
Output 
urgent task
medium task

// Task scheduler: CPU burst with priorities
const tasks = [['A', 3], ['B', 1], ['C', 2]]; // [name, priority]
const scheduler = new PQ();
for (const [name, pri] of tasks) scheduler.enqueue(name, pri);
const order = [];
while (scheduler.size > 0) order.push(scheduler.dequeue()[1]);
console.log(order);
Output 
[ 'B', 'C', 'A' ]

Notes

| Operation | Best | Avg | Worst | Space | |----------|------|---------|---------|-------| | Enqueue | O(1) | O(log n)| O(log n)| O(n) | | Dequeue | O(log n)|O(log n)|O(log n)| O(1) | | Peek | O(1) | O(1) | O(1) | O(1) | Algorithms commonly using a priority queue: Dijkstra's shortest path, Prim's MST, A* search, Huffman coding, K-way merge, and median-of-stream (two PQs). JavaScript has no built-in PQ; implement via a binary heap.

See also