How to Build an O(log n) Priority Queue with a Binary Heap in JavaScript

Unlike a simple FIFO queue, a priority queue assigns a priority to each element and always dequeues the element with the highest priority first, making it a common interview topic.

Problem

Implement a priority queue with two operations: enqueue(val, prior) to insert an element with a given priority (higher numbers mean higher priority) and dequeue() to remove and return the value of the element with the highest priority. Both operations must run in O(log n) time.

Solution Idea

The key is to use a binary heap (a complete binary tree stored in an array). A max‑heap keeps the largest priority at the root, allowing both insertion (bubble‑up) and removal (swap‑root‑with‑last, pop, then bubble‑down) to be performed in logarithmic time.

Insertion (enqueue) steps:

Append the new element to the end of the array.

Repeatedly compare it with its parent; if its priority is larger, swap them (bubble‑up) until the heap property is restored.

Removal (dequeue) steps:

Swap the root element (highest priority) with the last element.

Remove the last element (the original root) from the array.

From the new root, repeatedly swap with the larger of its two children (bubble‑down) until the heap property is restored.

Illustrations of the bubble‑up and bubble‑down processes:

Code Implementation

class PriorityQueue {
    constructor() {
        // array to store heap elements
        this.arr = [];
    }

    // enqueue
    enqueue(val, prior) {
        this.arr.push({ val: val, prior: prior });
        let cur = this.arr.length - 1;
        let temp = this.arr[cur];
        // bubble up
        for (let i = Math.floor((cur - 1) / 2); i >= 0; i = Math.floor((i - 1) / 2)) {
            if (temp.prior > this.arr[i].prior) {
                this.arr[cur] = this.arr[i];
                cur = i;
            } else break;
        }
        this.arr[cur] = temp;
    }

    // dequeue
    dequeue() {
        if (this.arr.length === 0) throw new Error("Queue is empty, cannot dequeue");
        // store result
        let res = this.arr[0].val;
        // move last element to root
        this.arr[0] = this.arr[this.arr.length - 1];
        // shrink array
        this.arr.length -= 1;
        // bubble down
        let cur = 0,
            len = this.arr.length;
        let temp = this.arr[0];
        for (let i = 2 * cur + 1; i < len; i = 2 * cur + 1) {
            if (i + 1 < len && this.arr[i].prior < this.arr[i + 1].prior) i++;
            if (temp.prior < this.arr[i].prior) {
                this.arr[cur] = this.arr[i];
                cur = i;
            } else break;
        }
        this.arr[cur] = temp;
        return res;
    }
}

let p = new PriorityQueue();
p.enqueue(5, 6);
p.enqueue(2, 100);
p.enqueue(90, 1);
console.log(p.dequeue()); // 2
console.log(p.dequeue()); // 5
console.log(p.dequeue()); // 90