Technical Concepts

Appearance

Heaps ​

Introduction ​

A heap is a specialized tree-based data structure that satisfies the "heap property": in a max-heap, every parent node is greater than or equal to its children; in a min-heap, every parent node is less than or equal to its children. Heaps are the backbone of priority queues and are essential for efficiently finding the smallest or largest element in a collection — an operation that comes up constantly in scheduling, graph algorithms, and stream processing. If you've ever wondered how your operating system decides which process to run next, there's a good chance a heap is involved.

Core Concepts ​

What Problem Does a Heap Solve? ​

Imagine you run a hospital emergency room. Patients arrive continuously, each with a different severity level. You always need to treat the most critical patient next, but new patients keep showing up. You could sort the entire list every time someone arrives, but that's expensive. What you really want is a structure that:

  1. Lets you insert a new patient quickly.
  2. Lets you extract the highest-priority patient quickly.
  3. Lets you peek at who's next without removing them.

A heap does all three of these in O(log n) time for insert and extract, and O(1) for peek. Compare that to a sorted array where insertion alone costs O(n).

The Heap Property ​

A heap is a complete binary tree — every level is fully filled except possibly the last, which is filled from left to right. This completeness is what lets us represent the entire tree as a flat array with no wasted space.

  • Min-Heap: parent <= children — the root is always the minimum element.
  • Max-Heap: parent >= children — the root is always the maximum element.

Array Representation ​

The beauty of a heap is that you don't need pointers or node objects. A simple array is enough. For a node at index i (0-based):

RelationshipIndex Formula
ParentMath.floor((i - 1) / 2)
Left child2 * i + 1
Right child2 * i + 2

Key Operations ​

Bubble Up (Sift Up) ​

When you insert a new element, you place it at the end of the array (the next available slot in the complete tree) and then repeatedly swap it with its parent as long as the heap property is violated.

Bubble Down (Sift Down) ​

When you extract the root (min or max), you replace it with the last element and then repeatedly swap it with its smallest (min-heap) or largest (max-heap) child until the heap property is restored.

Implementation: MinHeap in JavaScript ​

Let's build a complete, runnable MinHeap class from scratch.

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

  // Helper methods
  getParentIndex(i) { return Math.floor((i - 1) / 2); }
  getLeftChildIndex(i) { return 2 * i + 1; }
  getRightChildIndex(i) { return 2 * i + 2; }

  hasParent(i) { return this.getParentIndex(i) >= 0; }
  hasLeftChild(i) { return this.getLeftChildIndex(i) < this.heap.length; }
  hasRightChild(i) { return this.getRightChildIndex(i) < this.heap.length; }

  parent(i) { return this.heap[this.getParentIndex(i)]; }
  leftChild(i) { return this.heap[this.getLeftChildIndex(i)]; }
  rightChild(i) { return this.heap[this.getRightChildIndex(i)]; }

  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  // O(1) — look at the smallest element
  peek() {
    if (this.heap.length === 0) {
      throw new Error('Heap is empty');
    }
    return this.heap[0];
  }

  // O(log n) — add a new element
  insert(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }

  // O(log n) — remove and return the smallest element
  extractMin() {
    if (this.heap.length === 0) {
      throw new Error('Heap is empty');
    }
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return min;
  }

  bubbleUp(index) {
    while (this.hasParent(index) && this.parent(index) > this.heap[index]) {
      const parentIdx = this.getParentIndex(index);
      this.swap(parentIdx, index);
      index = parentIdx;
    }
  }

  bubbleDown(index) {
    while (this.hasLeftChild(index)) {
      let smallerChildIndex = this.getLeftChildIndex(index);

      if (
        this.hasRightChild(index) &&
        this.rightChild(index) < this.leftChild(index)
      ) {
        smallerChildIndex = this.getRightChildIndex(index);
      }

      if (this.heap[index] <= this.heap[smallerChildIndex]) {
        break;
      }

      this.swap(index, smallerChildIndex);
      index = smallerChildIndex;
    }
  }

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

// --- Demo ---
const heap = new MinHeap();
[15, 10, 20, 17, 8, 25, 3].forEach(v => heap.insert(v));

console.log('Heap contents:', heap.heap);
console.log('Min element:', heap.peek()); // 3

console.log('Extracting in order:');
while (heap.size() > 0) {
  console.log(heap.extractMin());
}
// Output: 3, 8, 10, 15, 17, 20, 25

Implementation: MaxHeap in JavaScript ​

A max-heap only differs from a min-heap in the comparison direction. Rather than duplicating everything, we can build one by flipping the comparisons:

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

  getParentIndex(i) { return Math.floor((i - 1) / 2); }
  getLeftChildIndex(i) { return 2 * i + 1; }
  getRightChildIndex(i) { return 2 * i + 2; }

  hasParent(i) { return this.getParentIndex(i) >= 0; }
  hasLeftChild(i) { return this.getLeftChildIndex(i) < this.heap.length; }
  hasRightChild(i) { return this.getRightChildIndex(i) < this.heap.length; }

  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  peek() {
    if (this.heap.length === 0) throw new Error('Heap is empty');
    return this.heap[0];
  }

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

  extractMax() {
    if (this.heap.length === 0) throw new Error('Heap is empty');
    const max = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return max;
  }

  bubbleUp(index) {
    while (
      this.hasParent(index) &&
      this.heap[this.getParentIndex(index)] < this.heap[index]
    ) {
      const parentIdx = this.getParentIndex(index);
      this.swap(parentIdx, index);
      index = parentIdx;
    }
  }

  bubbleDown(index) {
    while (this.hasLeftChild(index)) {
      let largerChildIndex = this.getLeftChildIndex(index);

      if (
        this.hasRightChild(index) &&
        this.heap[this.getRightChildIndex(index)] > this.heap[largerChildIndex]
      ) {
        largerChildIndex = this.getRightChildIndex(index);
      }

      if (this.heap[index] >= this.heap[largerChildIndex]) break;

      this.swap(index, largerChildIndex);
      index = largerChildIndex;
    }
  }

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

// --- Demo ---
const maxHeap = new MaxHeap();
[15, 10, 20, 17, 8, 25, 3].forEach(v => maxHeap.insert(v));
console.log('Max element:', maxHeap.peek()); // 25

Building a Heap from an Array: Heapify ​

Inserted elements one-by-one costs O(n log n). But there's a clever trick: you can convert an entire array into a heap in O(n) time by starting from the last non-leaf node and sifting down.

javascript
function heapifyArray(arr) {
  // Start from the last non-leaf node and work backwards
  const n = arr.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(arr, n, i);
  }
  return arr;
}

function siftDown(arr, size, index) {
  let smallest = index;
  const left = 2 * index + 1;
  const right = 2 * index + 2;

  if (left < size && arr[left] < arr[smallest]) {
    smallest = left;
  }
  if (right < size && arr[right] < arr[smallest]) {
    smallest = right;
  }
  if (smallest !== index) {
    [arr[index], arr[smallest]] = [arr[smallest], arr[index]];
    siftDown(arr, size, smallest);
  }
}

// --- Demo ---
const data = [15, 10, 20, 17, 8, 25, 3];
console.log('Before heapify:', data);
heapifyArray(data);
console.log('After heapify:', data); // [3, 8, 20, 17, 10, 25, 15]

Why is this O(n) instead of O(n log n)? The intuition is that most nodes are near the bottom of the tree and only need to sift down a short distance. Leaf nodes (half the array) don't move at all. Search for "build heap time complexity proof" for the full mathematical argument.

HeapSort ​

HeapSort uses a max-heap to sort an array in-place in O(n log n) time. It's not as cache-friendly as QuickSort, but it has a guaranteed worst-case of O(n log n) — no degenerate cases.

javascript
function heapSort(arr) {
  const n = arr.length;

  // Build max-heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDownMax(arr, n, i);
  }

  // Extract elements one by one
  for (let i = n - 1; i > 0; i--) {
    // Move current root (max) to end
    [arr[0], arr[i]] = [arr[i], arr[0]];
    // Sift down on the reduced heap
    siftDownMax(arr, i, 0);
  }

  return arr;
}

function siftDownMax(arr, size, index) {
  let largest = index;
  const left = 2 * index + 1;
  const right = 2 * index + 2;

  if (left < size && arr[left] > arr[largest]) largest = left;
  if (right < size && arr[right] > arr[largest]) largest = right;

  if (largest !== index) {
    [arr[index], arr[largest]] = [arr[largest], arr[index]];
    siftDownMax(arr, size, largest);
  }
}

// --- Demo ---
const arr = [12, 11, 13, 5, 6, 7];
console.log('Before:', arr);
heapSort(arr);
console.log('After:', arr); // [5, 6, 7, 11, 12, 13]

Classic Interview Problem: K Largest Elements ​

One of the most common heap interview questions: "Find the K largest elements in an unsorted array." The trick is to use a min-heap of size K.

javascript
function kLargest(arr, k) {
  const minHeap = new MinHeap();

  for (const num of arr) {
    if (minHeap.size() < k) {
      minHeap.insert(num);
    } else if (num > minHeap.peek()) {
      minHeap.extractMin();
      minHeap.insert(num);
    }
  }

  const result = [];
  while (minHeap.size() > 0) {
    result.push(minHeap.extractMin());
  }
  return result;
}

// --- Demo (assumes MinHeap class from above is available) ---
console.log(kLargest([3, 1, 5, 12, 2, 11, 9], 3)); // [9, 11, 12]

This runs in O(n log k) time and O(k) space — much better than sorting the entire array when k is small.

Time Complexity Summary ​

OperationTime ComplexityNotes
peek()O(1)Root is always min/max
insert()O(log n)Bubble up at most tree height
extractMin/Max()O(log n)Bubble down at most tree height
heapify (build)O(n)Bottom-up construction
heapSortO(n log n)Build + n extractions
Find K largest/smallestO(n log k)Maintain heap of size k

Real-World Applications ​

Best Practices ​

  1. Choose the right heap type: Use a min-heap when you need quick access to the smallest element (e.g., Dijkstra's algorithm) and a max-heap for the largest (e.g., scheduling by priority).
  2. Use a min-heap of size K for "top-K" problems: This is counterintuitive — you'd think you'd need a max-heap — but a small min-heap lets you discard elements smaller than the current Kth largest.
  3. Prefer heapify over repeated inserts: Building a heap from an existing array with heapify is O(n), while inserting n elements one by one is O(n log n).
  4. Use built-in priority queues in production: JavaScript doesn't have one natively, but Java has PriorityQueue, Python has heapq, and C++ has priority_queue. Use these in production; write your own for interviews.
  5. Remember that heaps are NOT fully sorted: A common misconception. The only guarantee is the root relationship with children — siblings have no ordering between them.
  6. Consider a heap for merge operations: When merging K sorted lists or streams, a min-heap of size K keeps track of the current smallest element across all sources.
  7. Watch for off-by-one errors: The array-based representation with 0-based indexing (parent at (i-1)/2) vs 1-based indexing (parent at i/2) is a frequent source of bugs.
  8. Two heaps for the running median: Maintain a max-heap for the lower half and a min-heap for the upper half. The median is always accessible from the roots. This is a classic interview pattern.
  • Binary Trees — Heaps are complete binary trees, so understanding tree traversal and structure helps.
  • Priority Queues — The abstract data type that heaps most commonly implement.
  • Graphs (Dijkstra's Algorithm) — Dijkstra's shortest-path algorithm relies on a min-heap (priority queue) for efficient vertex selection.
  • Sorting Algorithms — HeapSort is one of the fundamental comparison-based sorting algorithms alongside QuickSort and MergeSort.
  • Binary Search Trees — Often confused with heaps, but BSTs maintain a different ordering invariant (left < parent < right) and support ordered traversal.
  • Arrays — The underlying storage mechanism for heaps; understanding array indexing is essential.

Practice Problems ​

Here are problems from popular platforms to solidify your understanding:

LeetCode ​

HackerRank ​

Start with QHEAP1 and Kth Largest Element in a Stream to build confidence, then tackle the median and merge problems for interview-level preparation.