Heaps & Priority Queues

What is a Heap?

A heap is a complete binary tree that satisfies the heap property. In a Min Heap, every parent is less than or equal to its children, so the minimum value is always at the root. In a Max Heap, every parent is greater than or equal to its children, keeping the maximum at the root.

Heaps are the go-to data structure for priority queues — situations where you always want efficient access to the most important (highest or lowest priority) item. Common real-world uses include task scheduling, Dijkstra's shortest path, and the heap sort algorithm.

Heap as an Array

Although heaps are conceptually trees, they are stored in a flat array using a simple index formula:

• For node at index i: left child = 2i + 1, right child = 2i + 2
• Parent of node at index i: Math.floor((i - 1) / 2)

// Min Heap array: [1, 3, 5, 7, 9, 8]
//         1
//        / \
//       3   5
//      / \ /
//     7  9 8

Min Heap Implementation

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

  // O(log n) — push to end, then bubble up
  insert(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIdx = Math.floor((index - 1) / 2);
      if (this.heap[parentIdx] <= this.heap[index]) break;
      [this.heap[parentIdx], this.heap[index]] =
        [this.heap[index], this.heap[parentIdx]];
      index = parentIdx;
    }
  }

  // O(1) — root is always the minimum
  peek() {
    return this.heap[0] ?? null;
  }

  // O(log n) — remove root, put last element at root, bubble down
  extractMin() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return min;
  }

  bubbleDown(index) {
    const n = this.heap.length;
    while (true) {
      let smallest = index;
      const left  = 2 * index + 1;
      const right = 2 * index + 2;

      if (left  < n && this.heap[left]  < this.heap[smallest]) smallest = left;
      if (right < n && this.heap[right] < this.heap[smallest]) smallest = right;
      if (smallest === index) break;

      [this.heap[index], this.heap[smallest]] =
        [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }

  size() { return this.heap.length; }
}

const heap = new MinHeap();
[5, 3, 8, 1, 7].forEach(v => heap.insert(v));
console.log(heap.peek());       // 1
console.log(heap.extractMin()); // 1
console.log(heap.peek());       // 3

Priority Queue Pattern

For objects, compare by a priority field:

// Min-priority queue (lowest priority number = processed first)
class PriorityQueue {
  constructor() { this.heap = []; }

  enqueue(item, priority) {
    this.heap.push({ item, priority });
    this.bubbleUp(this.heap.length - 1);
  }

  dequeue() {
    if (!this.heap.length) return null;
    const min = this.heap[0].item;
    this.heap[0] = this.heap.pop();
    if (this.heap.length) this.bubbleDown(0);
    return min;
  }

  bubbleUp(i) {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.heap[p].priority <= this.heap[i].priority) break;
      [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
      i = p;
    }
  }

  bubbleDown(i) {
    const n = this.heap.length;
    while (true) {
      let min = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < n && this.heap[l].priority < this.heap[min].priority) min = l;
      if (r < n && this.heap[r].priority < this.heap[min].priority) min = r;
      if (min === i) break;
      [this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]];
      i = min;
    }
  }
}