Binary Heaps and Priority Queues via JavaScript

Concepts

A binary heap is a specialized tree-based data structure that satisfies the heap property: every parent node is either greater than (max heap) or less than (min heap) its children. A binary heap is always a complete binary tree, which makes an array the most compact and efficient representation. When you need a priority queue in JavaScript without a library, a binary heap JavaScript implementation is usually the best choice.

Key terms: complete binary tree, heap property, sift up (bubble up), sift down (sink down). For a max heap the root is the largest element; for a min heap the root is the smallest.

Array layout and index formulas

Storing a heap in an array follows a strict ordering: nodes are placed left-to-right on each level before moving to the next level. This yields constant-time formulas for parent and child indices:

• Left child index = 2n + 1
• Right child index = 2n + 2
• Parent index = Math.floor((n - 1) / 2) — often written as (n - 1) / 2

These formulas let you implement a binary heap array implementation JavaScript projects can use directly.

Max binary heap implementation

The following code shows a compact, readable implementation of a max heap in JavaScript. It demonstrates insert (bubble up), extractMax (sink down), peek, and size operations. This is a good starting point for a binary heap implementation in JavaScript or to build a priority queue in JavaScript using heap logic.

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

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

  peek() {
    return this.data[0] ?? null;
  }

  insert(value) {
    this.data.push(value);
    this._siftUp(this.data.length - 1);
  }

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

  extractMax() {
    if (!this.data.length) return null;
    const max = this.data[0];
    const last = this.data.pop();
    if (this.data.length) {
      this.data[0] = last;
      this._siftDown(0);
    }
    return max;
  }

  _siftDown(idx) {
    const len = this.data.length;
    while (true) {
      const left = 2 * idx + 1;
      const right = 2 * idx + 2;
      let swap = null;

      if (left < len && this.data[left] > this.data[idx]) swap = left;
      if (
        right < len &&
        ((swap === null && this.data[right] > this.data[idx]) ||
          (swap !== null && this.data[right] > this.data[left]))
      ) {
        swap = right;
      }

      if (swap === null) break;
      [this.data[idx], this.data[swap]] = [this.data[swap], this.data[idx]];
      idx = swap;
    }
  }
}

// Example usage
const heap = new MaxBinaryHeap();
heap.insert(3);
heap.insert(4);
heap.insert(31);
heap.insert(6);
console.log(heap.data); // e.g. [31, 6, 4, 3]
console.log(heap.extractMax()); // 31

Insert (bubble up)

When a new value is added we push it to the end of the array then bubble it up until the heap property is restored. This operation is often called max heap bubble up JavaScript in tutorials and runs in O(log n) time.

Extract max (sink down)

To remove the maximum element we replace the root with the last element and then sink it down, swapping with the larger of its children until it finds the correct position. This is commonly referenced as extractMax binary heap JavaScript and also runs in O(log n).

Heapify (build heap) and time complexity

You can turn an arbitrary array into a heap in-place with a heapify algorithm JavaScript developers use when performance matters. The trick is to call sift-down starting from the last non-leaf node down to the root. That builds a heap in O(n) time, which is faster than inserting each element one-by-one (O(n log n)).

Complexities at a glance:

• Insert / enqueue: O(log n)
• Extract max / dequeue: O(log n)
• Peek (top): O(1)
• Build heap (heapify): O(n)

// Heapify example (in-place)
function heapify(array) {
  const n = array.length;
  const heap = { data: array, _siftDown: function(i) {
    const len = this.data.length;
    while (true) {
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      let swap = null;
      if (left < len && this.data[left] > this.data[i]) swap = left;
      if (right < len && ((swap === null && this.data[right] > this.data[i]) || (swap !== null && this.data[right] > this.data[left]))) swap = right;
      if (swap === null) break;
      [this.data[i], this.data[swap]] = [this.data[swap], this.data[i]];
      i = swap;
    }
  }};

  for (let i = Math.floor((n - 1) / 2); i >= 0; i--) {
    heap._siftDown(i);
  }
  return heap.data; // now a max heap
}

Priority queue using a heap

A binary heap pairs perfectly with a priority queue because it can always return the highest-priority item quickly. Here is a simple priority queue implementation that stores nodes and orders them by a numeric priority.

class PQNode {
  constructor(value, priority) {
    this.value = value;
    this.priority = priority;
  }
}

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

  enqueue(value, priority) {
    const node = new PQNode(value, priority);
    this.heap.push(node);
    this._siftUp(this.heap.length - 1);
  }

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

  dequeue() {
    if (!this.heap.length) return null;
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length) {
      this.heap[0] = last;
      this._siftDown(0);
    }
    return top.value;
  }

  _siftDown(idx) {
    const len = this.heap.length;
    while (true) {
      const left = 2 * idx + 1;
      const right = 2 * idx + 2;
      let swap = null;
      if (left < len && this.heap[left].priority > this.heap[idx].priority) swap = left;
      if (
        right < len &&
        ((swap === null && this.heap[right].priority > this.heap[idx].priority) ||
          (swap !== null && this.heap[right].priority > this.heap[left].priority))
      ) {
        swap = right;
      }
      if (swap === null) break;
      [this.heap[idx], this.heap[swap]] = [this.heap[swap], this.heap[idx]];
      idx = swap;
    }
  }
}

// Example: priority queue in JavaScript using heap
const pq = new PriorityQueue();
pq.enqueue('task1', 2);
pq.enqueue('urgent', 5);
pq.enqueue('later', 1);
console.log(pq.dequeue()); // 'urgent'

When to use a binary heap

Binary heaps are ideal when you need a priority queue: scheduling tasks, event simulation, or algorithms like Dijkstra's algorithm that require repeatedly extracting the next-best node. The compact array layout and efficient sift operations make the binary heap a practical heap data structure for JavaScript developers.

Min heap vs max heap and final notes

Converting the max heap samples above into a min heap (min heap vs max heap JavaScript example) is straightforward: change comparison operators so parents are less than their children. You can also adapt the same array-based heap to support custom comparator functions for complex priority rules.

Tip: For integer index math remember the common formulas: parent = Math.floor((n - 1) / 2), left = 2n + 1, right = 2n + 2.

Use these patterns to implement a robust binary heap JavaScript solution: whether you need a binary heap insert and extract JavaScript functions, a binary heap array implementation JavaScript-friendly, or a priority queue enqueue dequeue JavaScript API, a heap-based approach is efficient and widely applicable.