Implementing Priority Queues with NodeJS and Javascript

A normal queue is FIFO. A priority queue serves higher (or lower) priority first — triage, critical jobs, schedulers. Built on the min-heap from ep. 9.

What you'll learn:

• enqueue/dequeue by priority
• Reusing a heap in an array
• min-heap vs max-heap for business rules

Prerequisites: heaps (ep. 9).

Priority queue: heap with explicit priority

In the previous post we talked about Heaps—and now we are building on top of that. Priority Queues are a data structure backed by Heaps, so if you haven't read that post yet I'd recommend going through it first, we are going to lean on a lot of the same concepts here.

If Priority Queues are based on Heaps, you've probably already figured out that they use a tree structure underneath—binary trees, remember? If not, check the Trees post for a refresher. The short version: binary trees are ones where all elements smaller than the root go to one side, and all larger elements go to the other. In a Priority Queue we follow the same logic, but the ordering is not by the element's raw value—it's by its priority.

sequenceDiagram
  participant C as Caller
  participant PQ as PriorityQueue
  C->>PQ: enqueue(element, priority)
  Note over PQ: heapifyUp — bubble to correct spot
  C->>PQ: dequeue()
  Note over PQ: remove root (highest priority)
  Note over PQ: heapifyDown — restore order
  PQ-->>C: element

In a Priority Queue the root is always the element with the lowest priority number (if we follow a min-heap approach where 1 = most urgent) or the highest priority number (max-heap). This means that whenever we call dequeue, we always get the most important item back—regardless of when it was inserted.

Hands-on

First The Theory

A regular queue is FIFO: first in, first out. A Priority Queue breaks that contract. The element that comes out first is the one with the highest priority, no matter when it joined the queue.

Think of an emergency room: a patient with a broken finger waits, while someone with a heart attack is seen immediately. The arrival time doesn't matter—priority does.

The reason we back this with a Heap (instead of a sorted array) is performance. Inserting into a sorted array is O(n)—you have to find the right spot. With a heap-backed priority queue, enqueue and dequeue are both O(log n).

Now The Practice

Open your favourite IDE, create a file called priority-queue.js, and paste the code below:

class PriorityQueue {
  constructor() {
    this.heap = []
  }
 
  getParentIndex(i) {
    return Math.floor((i - 1) / 2)
  }
  getLeftChildIndex(i) {
    return 2 * i + 1
  }
  getRightChildIndex(i) {
    return 2 * i + 2
  }
 
  enqueue(element, priority) {
    this.heap.push({ element, priority })
    this.heapifyUp()
  }
 
  dequeue() {
    const min = this.heap[0]
    this.heap[0] = this.heap.pop()
    this.heapifyDown()
    return min.element
  }
 
  isEmpty() {
    return this.heap.length === 0
  }
}

Breaking down what we have so far:

• The PriorityQueue class initialises heap as an empty array. Yes, it's called a Priority Queue, but the internal structure is still a Heap.
• getParentIndex, getLeftChildIndex, and getRightChildIndex are the same index helpers from the Heaps post.
• enqueue is our "add to queue" method. Unlike insert, it takes both an element and its priority. Without the priority, the magic can't happen.
• dequeue removes (and returns) the highest-priority element—always from the root.
• isEmpty is a simple utility to check whether the queue has anything left.

With just this we can't see the full picture yet. We need the heapifyUp and heapifyDown functions. Let's add them.

heapifyUp bubbles a newly inserted element up the tree until it finds its correct position based on priority. Paste this after isEmpty:

  heapifyUp() {
    let index = this.heap.length - 1
    while (
      index !== 0 &&
      this.heap[this.getParentIndex(index)].priority > this.heap[index].priority
    ) {
      ;[this.heap[this.getParentIndex(index)], this.heap[index]] = [
        this.heap[index],
        this.heap[this.getParentIndex(index)],
      ]
      index = this.getParentIndex(index)
    }
  }

heapifyDown pushes the replacement root down the tree after a dequeue. Paste this after heapifyUp:

  heapifyDown() {
    let index = 0
    while (this.getLeftChildIndex(index) < this.heap.length) {
      let smallerChildIndex = this.getLeftChildIndex(index)
      if (
        this.getRightChildIndex(index) < this.heap.length &&
        this.heap[this.getRightChildIndex(index)].priority <
          this.heap[smallerChildIndex].priority
      ) {
        smallerChildIndex = this.getRightChildIndex(index)
      }
      if (this.heap[index].priority < this.heap[smallerChildIndex].priority) break
      ;[this.heap[index], this.heap[smallerChildIndex]] = [
        this.heap[smallerChildIndex],
        this.heap[index],
      ]
      index = smallerChildIndex
    }
  }

ALMOST DONE, I PROMISE!

With everything in place, let's create some items in the queue and see if it's all working as expected. After the PriorityQueue class, add this:

const priorityQueue = new PriorityQueue()
 
priorityQueue.enqueue(15, 1)
console.log(`Priority queue (enqueue 15, priority 1):`, { queue: priorityQueue.heap })
 
priorityQueue.enqueue(10, 2)
console.log(`Priority queue (enqueue 10, priority 2):`, { queue: priorityQueue.heap })
 
priorityQueue.enqueue(5, 3)
console.log(`Priority queue (enqueue 5, priority 3):`, { queue: priorityQueue.heap })
 
priorityQueue.enqueue(20, 4)
console.log(`Priority queue (enqueue 20, priority 4):`, { queue: priorityQueue.heap })
 
priorityQueue.enqueue(7, 5)
console.log(`Priority queue (enqueue 7, priority 5):`, { queue: priorityQueue.heap })
 
priorityQueue.enqueue(25, 6)
console.log(`Priority queue (enqueue 25, priority 6):`, { queue: priorityQueue.heap })
 
priorityQueue.enqueue(1, 7)
console.log(`Priority queue (enqueue 1, priority 7):`, { queue: priorityQueue.heap })

Breaking it down:

• We create a new PriorityQueue instance.
• We enqueue elements with different priorities. Notice that priority: 1 means most urgent here (min-heap).
• We log the queue state after each enqueue so we can see the heap reshaping itself.

Now let's verify the dequeue order. Add this after the enqueues:

console.log(`dequeue 1/3:`, {
  rootValue: priorityQueue.dequeue(),
  heap: priorityQueue.heap,
})
 
console.log(`dequeue 2/3:`, {
  rootValue: priorityQueue.dequeue(),
  heap: priorityQueue.heap,
})
 
console.log(`dequeue 3/3:`, {
  rootValue: priorityQueue.dequeue(),
  heap: priorityQueue.heap,
})

Run the file:

node priority-queue.js

The dequeue logs should look roughly like this:

dequeue 1/3: {
  rootValue: 15,
  heap: [
    { element: 10, priority: 2 },
    { element: 20, priority: 4 },
    { element: 5, priority: 3 },
    { element: 1, priority: 7 },
    { element: 7, priority: 5 },
    { element: 25, priority: 6 }
  ]
}
dequeue 2/3: {
  rootValue: 10,
  heap: [
    { element: 5, priority: 3 },
    { element: 20, priority: 4 },
    { element: 25, priority: 6 },
    { element: 1, priority: 7 },
    { element: 7, priority: 5 }
  ]
}
dequeue 3/3: {
  rootValue: 5,
  heap: [
    { element: 20, priority: 4 },
    { element: 7, priority: 5 },
    { element: 25, priority: 6 },
    { element: 1, priority: 7 }
  ]
}

AWESOME!

Each dequeue returns the element with the lowest priority number first—15 (priority 1), then 10 (priority 2), then 5 (priority 3). That's exactly the behaviour we wanted. The heap restructures itself after each removal so the next most urgent item floats up to the root.

This implementation follows a min-heap approach, meaning the element with the smallest priority number is processed first (priority 1 = most urgent). If you want a max-heap instead—where the largest priority number is most urgent—just flip the comparison operators in heapifyUp and heapifyDown.

What if two elements have the same priority?

Great question. In this implementation, equal-priority elements will both end up near the top of the heap, but the order between them is not guaranteed. If you need stable ordering for ties, you can add a secondary sort key—like an insertion timestamp—and compare by that when priorities are equal.

Edge cases: changing priority mid-flight

Updating an item's priority in the middle requires re-heapifying or remove+reinsert.

Tie-breaking: define FIFO by timestamp in the comparator or order is undefined.

TL;DR — Priority queue

Next steps

• BST (ep. 12)
• Maps and Sets (ep. 11)

Before you go

Used Bull, a custom heap, or something else for job priority? Comment below.