Heap

Explanation

Heaps are most often implemented as arrays rather than linked tree nodes, taking advantage of a mathematical property of complete binary trees: for a node at index i, its left child is at 2i+1, its right child is at 2i+2, and its parent is at floor((i-1)/2). This means you can traverse the "tree" using arithmetic on array indices — no pointers needed. The two core operations are insert and extractMin/extractMax. Insert adds the element at the end of the array (maintaining completeness) and then "bubbles up" — swapping the new element with its parent while it violates the heap property. ExtractMin removes the root, replaces it with the last element, and "sifts down" — swapping with the smaller child until the heap property is restored. Both operations are O(log n) because they traverse at most one root-to-leaf path. The killer application is the priority queue: a data structure that always gives you the highest-priority item next. In a min-heap, "highest priority" means smallest value; in a max-heap, it means largest. Priority queues power: Dijkstra's shortest path algorithm (always processes the unvisited node with the smallest known distance), A* pathfinding, task schedulers (run the highest-priority task next), and heap sort (O(n log n), in-place). JavaScript has no built-in heap; you'll implement one from scratch in interviews or use a library. Python's heapq module provides a min-heap on a list. Java has PriorityQueue.

Code Example

// Min-heap implementation in JavaScript
class MinHeap {
  #data = [];

  push(val) {
    this.#data.push(val);
    this.#bubbleUp(this.#data.length - 1);
  }

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

  peek() { return this.#data[0]; }
  size() { return this.#data.length; }

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

  #siftDown(i) {
    const n = this.#data.length;
    while (true) {
      let smallest = i;
      const l = 2*i+1, r = 2*i+2;
      if (l < n && this.#data[l] < this.#data[smallest]) smallest = l;
      if (r < n && this.#data[r] < this.#data[smallest]) smallest = r;
      if (smallest === i) break;
      [this.#data[smallest], this.#data[i]] = [this.#data[i], this.#data[smallest]];
      i = smallest;
    }
  }
}

const h = new MinHeap();
[5, 3, 8, 1, 4].forEach(v => h.push(v));
console.log(h.pop()); // 1
console.log(h.pop()); // 3

Why It Matters for Engineers

The heap is the data structure behind every "find the Nth largest/smallest" problem and every shortest-path algorithm. Understanding it means understanding why Dijkstra's runs in O((V+E) log V) rather than O(V²) — the heap turns a slow "scan all unvisited nodes to find the minimum" into a fast O(log V) extraction. Heap questions come up regularly in technical interviews because they test both data structure knowledge and the ability to implement non-trivial tree operations on arrays. Knowing the array representation and the bubble-up/sift-down operations cold is high-leverage interview preparation.