Heaps

What Is a Heap?

A heap is a complete binary tree that follows the heap property. In a max-heap, every parent is greater than or equal to its children. In a min-heap, every parent is smaller. That's the whole idea.

Heaps are stored as arrays, not as node objects with pointers. For a node at index i, its left child is at 2i+1 and its right child is at 2i+2. The parent is at Math.floor((i-1)/2). It's compact and cache-friendly.

The most important thing about a heap is that the root is always the maximum (or minimum) value. This makes heaps perfect for priority queues and heap sort.

Insert and Extract

Inserting into a heap means adding the element at the end, then "bubbling up" — swapping with its parent until the heap property is restored. It's like a heavy element sinking to the bottom in a max-heap.

Extracting the root means removing it, putting the last element in its place, then "sifting down" — swapping with the larger child until the heap property holds. The root always gives you the max (or min) value.

Both operations are O(log n) because you only traverse one path from root to leaf. That's pretty efficient for maintaining a sorted collection.

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

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

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

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

  siftDown(idx) {
    const length = this.data.length;
    while (true) {
      let largest = idx;
      const left = 2 * idx + 1;
      const right = 2 * idx + 2;

      if (left < length && this.data[left] > this.data[largest]) {
        largest = left;
      }
      if (right < length && this.data[right] > this.data[largest]) {
        largest = right;
      }
      if (largest === idx) break;
      [this.data[idx], this.data[largest]] = [this.data[largest], this.data[idx]];
      idx = largest;
    }
  }
}

const heap = new MaxHeap();
[4, 10, 3, 5, 1].forEach(v => heap.insert(v));
console.log(heap.extractMax());
console.log(heap.extractMax());

Heap Sort and Priority Queues

Heap sort works by inserting all elements into a max-heap, then repeatedly extracting the maximum. You get a sorted array in O(n log n) time. It's not the fastest in practice (quicksort usually wins), but it's guaranteed O(n log n) with no worst-case surprises.

Priority queues are the real killer app for heaps. Instead of a regular FIFO queue, a priority queue always gives you the highest-priority element. Tasks with deadlines, event scheduling, Dijkstra's algorithm — they all use priority queues.

JavaScript doesn't have a built-in heap, but implementing one is straightforward. Once you have a heap, you can build priority queues, heapsort, and even solve top-K problems elegantly.

function heapSort(arr) {
  const heap = new MaxHeap();
  arr.forEach(v => heap.insert(v));

  const sorted = [];
  while (heap.data.length > 0) {
    sorted.push(heap.extractMax());
  }
  return sorted.reverse();
}

console.log(heapSort([5, 3, 8, 1, 9, 2]));