Heaps and Priority Queues

Written by Swapnil RajaUpdated 29 Aug 2026

JavaScript has no heap. You will have to write one, and it is the single most useful structure you can carry into an interview - it turns every 'top k' question from a sort into a scan.

What a heap guarantees

A min-heap keeps the smallest element at the root. Not a sorted list - just the guarantee that every parent is smaller than its children. That weaker promise is what makes it cheap to maintain.

Peek the smallest - O(1).
Insert - O(log n).
Remove the smallest - O(log n).
Build from n items - O(n).

Stored as a flat array

A heap is a complete binary tree, so it needs no node objects. Positions are arithmetic:

The index maths

javascript

// For the element at index i:
const parent = (i) => Math.floor((i - 1) / 2)
const left   = (i) => 2 * i + 1
const right  = (i) => 2 * i + 2

//        1            index 0
//      /   \
//     3     5         index 1, 2
//    / \
//   4   8             index 3, 4
// stored as: [1, 3, 5, 4, 8]

console.log(parent(5), left(2), right(2))  // 2 5 6

A working min-heap

MinHeap

javascript

class MinHeap {
  #items = []

  get size() { return this.#items.length }
  peek() { return this.#items[0] }

  push(value) {
    this.#items.push(value)
    this.#bubbleUp(this.#items.length - 1)
  }

  pop() {
    if (this.#items.length === 0) return undefined
    const top = this.#items[0]
    const last = this.#items.pop()

    if (this.#items.length > 0) {
      this.#items[0] = last
      this.#bubbleDown(0)
    }

    return top
  }

  #bubbleUp(i) {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2)
      if (this.#items[parent] <= this.#items[i]) break
      this.#swap(parent, i)
      i = parent
    }
  }

  #bubbleDown(i) {
    const n = this.#items.length

    while (true) {
      const left = 2 * i + 1
      const right = 2 * i + 2
      let smallest = i

      if (left < n && this.#items[left] < this.#items[smallest]) smallest = left
      if (right < n && this.#items[right] < this.#items[smallest]) smallest = right
      if (smallest === i) break

      this.#swap(i, smallest)
      i = smallest
    }
  }

  #swap(a, b) {
    ;[this.#items[a], this.#items[b]] = [this.#items[b], this.#items[a]]
  }
}

const heap = new MinHeap()
for (const n of [5, 3, 8, 1]) heap.push(n)
console.log(heap.pop(), heap.pop())  // 1 3

A max-heap, without rewriting it

Push negated values into a min-heap and negate on the way out. For objects, pass a comparator instead.

Priority queue with a comparator

javascript

// A comparator-driven heap, complete and runnable on its own.
class PriorityQueue {
  #items = []
  #compare

  constructor(compare = (a, b) => a - b) { this.#compare = compare }

  get size() { return this.#items.length }
  peek() { return this.#items[0] }

  push(value) {
    this.#items.push(value)
    let i = this.#items.length - 1
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2)
      if (this.#compare(this.#items[parent], this.#items[i]) <= 0) break
      ;[this.#items[parent], this.#items[i]] = [this.#items[i], this.#items[parent]]
      i = parent
    }
  }

  pop() {
    if (this.#items.length === 0) return undefined
    const top = this.#items[0]
    const last = this.#items.pop()

    if (this.#items.length) {
      this.#items[0] = last
      let i = 0
      while (true) {
        const l = 2 * i + 1
        const r = 2 * i + 2
        let best = i
        if (l < this.#items.length && this.#compare(this.#items[l], this.#items[best]) < 0) best = l
        if (r < this.#items.length && this.#compare(this.#items[r], this.#items[best]) < 0) best = r
        if (best === i) break
        ;[this.#items[i], this.#items[best]] = [this.#items[best], this.#items[i]]
        i = best
      }
    }

    return top
  }
}

// Highest priority first.
const queue = new PriorityQueue((a, b) => b.priority - a.priority)
queue.push({ task: "low", priority: 1 })
queue.push({ task: "urgent", priority: 9 })
console.log(queue.pop())   // { task: "urgent", priority: 9 }

Where it earns its place

Anywhere you repeatedly need the current best without sorting everything: task schedulers, Dijkstra's algorithm, merging sorted streams, and every top-k question.

What a heap actually guarantees

Only that the root is the smallest - or largest - element. The rest is partially ordered, which is exactly why it is cheap. A sorted array gives you far more ordering than you need for "give me the next smallest", and charges O(n log n) up front for it.

peek - O(1). The answer is the root.
push - O(log n). Add at the end, swim up.
pop - O(log n). Move the last element to the root, sink down.
build from n items - O(n), not O(n log n), if you heapify in place.
search for an arbitrary value - O(n). A heap is not a lookup structure.

A working binary heap

Min-heap with an array

javascript

class MinHeap {
  constructor() { this.data = [] }

  push(value) {
    this.data.push(value)
    let i = this.data.length - 1
    while (i > 0) {
      const parent = (i - 1) >> 1
      if (this.data[parent] <= this.data[i]) break
      ;[this.data[parent], this.data[i]] = [this.data[i], this.data[parent]]
      i = parent
    }
  }

  pop() {
    if (this.data.length <= 1) return this.data.pop()
    const top = this.data[0]
    this.data[0] = this.data.pop()

    let i = 0
    for (;;) {
      const left = 2 * i + 1
      const right = left + 1
      let smallest = i
      if (left < this.data.length && this.data[left] < this.data[smallest]) smallest = left
      if (right < this.data.length && this.data[right] < this.data[smallest]) smallest = right
      if (smallest === i) break
      ;[this.data[smallest], this.data[i]] = [this.data[i], this.data[smallest]]
      i = smallest
    }

    return top
  }

  get size() { return this.data.length }
}

const heap = new MinHeap()
for (const n of [5, 1, 4, 2]) heap.push(n)
console.log(heap.pop(), heap.pop())  // 1 2

JavaScript has no built-in priority queue, so being able to write this from memory is worth more here than in languages that ship one.

PreviousThe Maths You Actually Need NextTop K Problems