Heaps

Complete binary trees that keep the smallest or largest value at the root and support fast priority operations.

What is it?

Heaps turn a binary tree into a priority queue: min-heaps always bubble the globally smallest value to the root; max-heaps do the same for the largest. Both structures maintain the heap property as elements are inserted or removed by bubbling values up or down along the tree, which makes inserts and extracts logarithmic. Because heaps are stored as arrays, they are cache-friendly and trivial to serialize, which is why interviewers love them for problems like "find the Kth largest", streaming medians, and event schedulers.

Time Complexity

AccessO(1) for peek

SearchO(n)

InsertionO(log n)

DeletionO(log n)

Implementation Example

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

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

  extractMin() {
    if (this.data.length === 0) return null;
    const min = this.data[0];
    const end = this.data.pop();
    if (this.data.length) {
      this.data[0] = end;
      this.#bubbleDown(0);
    }
    return min;
  }

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

  #bubbleDown(index) {
    const length = this.data.length;
    while (true) {
      let left = index * 2 + 1;
      let right = index * 2 + 2;
      let smallest = index;
      if (left < length && this.data[left] < this.data[smallest]) smallest = left;
      if (right < length && this.data[right] < this.data[smallest]) smallest = right;
      if (smallest === index) break;
      [this.data[index], this.data[smallest]] = [this.data[smallest], this.data[index]];
      index = smallest;
    }
  }
}

Heaps

Heaps Deep Dive

Heaps act as the backbone of priority queues, guaranteeing that inserts and extracts happen in logarithmic time while the best candidate sits at the root.

?But why does this matter?

Because heaps are stored as arrays, they stay cache-friendly and easy to ship across threads, making them perfect for top-K problems and weighted graph searches.

Visual Flow

How it actually moves

Insert (push)

O(log n)

Place value at the end of the array and bubble up until the heap property holds.

Extract min/max

O(log n)

Swap root with the tail, pop it, then bubble down the new root.

Peek

O(1)

The top element always lives at index 0.

Sift down (heapify)

Swap the root with the last element and remove the last element (this is the extracted value).

Set current index to 0 and loop while it has a child inside bounds.

Pick the smallest (min-heap) or largest (max-heap) child as the swap candidate.

If the candidate violates the heap property, swap and continue bubbling down; otherwise stop.

Heapify runs in O(log n); building a heap from scratch by heapifying bottom-up runs in O(n).

Watch the best explainer

Heap — Heap Sort — Heapify — Priority Queues

Abdul Bari

The definitive heap lecture: build, sift, sort, and priority queues on one whiteboard.

Think of a VIP waiting line

Everyone stands in order of urgency. When a more important guest arrives they bubble toward the front, and when the host calls someone they always take the current VIP.

Real-world analogy

Ride-hailing companies re-prioritize drivers as ETAs change, bubbling the closest driver to the top of a min-heap.

Takeaway

Heaps continuously maintain this ordering without resorting to full re-sorts, which is why they are staples in interviews.

Practical applications

• Dijkstra / A* frontier selection during pathfinding.
• Streaming “Top K” dashboards (e.g., most active customers).
• Median-of-data-stream using dual heaps.

Technical insights

• Binary heaps keep the tree complete, so nodes can be stored in arrays and accessed via index arithmetic.
• Min-heaps optimize for smallest-first problems (deadlines, costs), while max-heaps surface largest values (leaderboards).
• Fibonacci/Binomial heaps offer better theoretical bounds but binary heaps win in practice due to simple constants.

When to reach for it

• Greedy problems
• Top/Bottom K queries
• Priority scheduling

Operations Breakdown

Insert (push)

O(log n)

Place value at the end of the array and bubble up until the heap property holds.

Extract min/max

O(log n)

Swap root with the tail, pop it, then bubble down the new root.

Peek

O(1)

The top element always lives at index 0.

Best practices

• Reuse shared heap utilities so interview code stays concise and bug-free.
• Convert to max-heap by flipping comparisons or storing negated values when language defaults to min-heaps.
• Combine two heaps (min + max) to track medians or maintain sliding-window statistics.

Common pitfalls

• Calling extract on an empty heap should be guarded; returning undefined/null hides logic errors.
• Mixing comparable types (numbers vs objects) without a comparator leads to inconsistent ordering.
• Iterating through the heap array directly breaks the priority guarantee; always pop or clone first.

Every kind of Heaps

Interviewers rarely say which flavor they mean — they expect you to recognize it from the problem. Each variant below comes with the algorithms it unlocks.

Type 1 of 4

Binary Min / Max Heap

→ full page

A complete binary tree in an array: parent beats children. The root is always the extreme — everything else is only loosely ordered.

What to know

Array layout: children of i at 2i+1, 2i+2; parent at (i−1)/2. No pointers.
Sift-up on insert, sift-down on extract; both walk one root-to-leaf path.
Building from n items with sift-down is O(n), not O(n log n).
A max-heap is a min-heap on negated values.

Algorithms to reach for

Heapify (bottom-up build)

O(n)

Turn an array into a heap in linear time

Insert / extract root

O(log n)

Priority queue primitives

Heapsort

O(n log n)

Sort by repeated extraction

In the wild: Every language’s priority queue, OS schedulers, event loops, timer wheels.

Practice problems — hints, approach & solution on their own pages

Last Stone WeightEasy Kth Largest Element in an ArrayMedium

Type 2 of 4

Top-K Pattern (bounded heap)

→ full page

Keep a heap of size k that ejects the weakest member on overflow. Answers "k largest/smallest/most frequent" over huge or streaming data.

What to know

Counter-intuitive: use a MIN-heap of size k to track the k LARGEST items.
Memory stays O(k) no matter how big the stream — the whole point.
For k close to n, Quickselect on a materialized array is faster.

Algorithms to reach for

Top-K elements

O(n log k)

K most frequent / largest (LeetCode 347, 215)

K closest points

O(n log k)

Bounded max-heap by distance (LeetCode 973)

Streaming kth largest

O(log k) per item

Maintain kth largest as items arrive (LeetCode 703)

In the wild: Trending topics, "top 10" dashboards, nearest-neighbor shortlists, alert ranking.

Practice problems — hints, approach & solution on their own pages

Top K Frequent ElementsMedium K Closest Points to OriginMedium Kth Largest Element in a StreamEasy

Type 3 of 4

Two-Heaps Pattern

→ full page

A max-heap of the lower half and a min-heap of the upper half, kept balanced — their tops bracket the median at all times.

What to know

Rebalance whenever sizes differ by more than one.
Median = a root (odd count) or average of both roots (even count).
Sliding-window median adds lazy deletion with a hashmap of pending removals.

Algorithms to reach for

Find median from stream

O(log n)

O(log n) insert, O(1) median (LeetCode 295)

Sliding window median

O(n log k)

Median of each window with lazy deletes (LeetCode 480)

IPO / scheduling

O(n log n)

Alternate two heaps to maximize capital (LeetCode 502)

In the wild: Latency p50 monitoring, real-time analytics, load-balancer median tracking.

Practice problems — hints, approach & solution on their own pages

Find Median from Data StreamHard Sliding Window MedianHard IPOHard

Type 4 of 4

D-ary, Indexed & Mergeable Heaps

→ full page

Engineering variants: wider nodes (d-ary), position tracking for decrease-key (indexed), and heaps that merge in O(log n) (pairing, Fibonacci).

What to know

D-ary heaps trade deeper sift-downs for shallower trees — 4-ary often wins in practice for Dijkstra.
Indexed priority queues map item → heap position so priorities can be updated in place.
Fibonacci heaps give O(1) amortized decrease-key (theory); pairing heaps win in practice.

Algorithms to reach for

Dijkstra with decrease-key

O(E + V log V) w/ Fib

Update tentative distances in place

Pairing-heap meld

O(1) amortized

Merge two priority queues cheaply

D-ary sift tuning

O(log_d n) per op

Cache-tuned priority queues

In the wild: Network routing daemons, simulation engines merging event queues, game AI planners.

Practice problems — hints, approach & solution on their own pages

Network Delay TimeMedium Minimum Cost to Hire K WorkersHard

Signature algorithms

Algorithm

Min-heap priority queue

Guarantees access to the smallest element—useful for deadline scheduling, Dijkstra, and streaming medians.

Time

Insert O(log n), Extract O(log n)

Space

O(n)

class MinHeap {
  constructor() {
    this.data = [];
  }
  push(val) {
    this.data.push(val);
    this.#up(this.data.length - 1);
  }
  pop() {
    if (!this.data.length) return null;
    const min = this.data[0];
    const end = this.data.pop();
    if (this.data.length) {
      this.data[0] = end;
      this.#down(0);
    }
    return min;
  }
  #up(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;
    }
  }
  #down(i) {
    const n = this.data.length;
    while (true) {
      let left = i * 2 + 1;
      let right = i * 2 + 2;
      let smallest = i;
      if (left < n && this.data[left] < this.data[smallest]) smallest = left;
      if (right < n && this.data[right] < this.data[smallest]) smallest = right;
      if (smallest === i) break;
      [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
      i = smallest;
    }
  }
}

Algorithm

Max-heap priority queue

Mirror image of the min-heap that surfaces the largest value—handy for leaderboards and "k largest" queries.

Time

Insert O(log n), Extract O(log n)

Space

O(n)

class MaxHeap {
  constructor() {
    this.data = [];
  }
  push(val) {
    this.data.push(val);
    this.#up(this.data.length - 1);
  }
  pop() {
    if (!this.data.length) return null;
    const max = this.data[0];
    const end = this.data.pop();
    if (this.data.length) {
      this.data[0] = end;
      this.#down(0);
    }
    return max;
  }
  #up(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;
    }
  }
  #down(i) {
    const n = this.data.length;
    while (true) {
      let left = i * 2 + 1;
      let right = i * 2 + 2;
      let largest = i;
      if (left < n && this.data[left] > this.data[largest]) largest = left;
      if (right < n && this.data[right] > this.data[largest]) largest = right;
      if (largest === i) break;
      [this.data[i], this.data[largest]] = [this.data[largest], this.data[i]];
      i = largest;
    }
  }
}

Algorithm

Kth largest via heap

Maintain a min-heap of size K while scanning the input; the root is always the Kth largest so far.

Time

O(n log k)

Space

O(k)

function kthLargest(nums, k) {
  const heap = [];
  const bubbleUp = (idx) => {
    while (idx > 0) {
      const parent = Math.floor((idx - 1) / 2);
      if (heap[parent] <= heap[idx]) break;
      [heap[parent], heap[idx]] = [heap[idx], heap[parent]];
      idx = parent;
    }
  };
  const bubbleDown = (idx) => {
    const n = heap.length;
    while (true) {
      let left = idx * 2 + 1;
      let right = idx * 2 + 2;
      let smallest = idx;
      if (left < n && heap[left] < heap[smallest]) smallest = left;
      if (right < n && heap[right] < heap[smallest]) smallest = right;
      if (smallest === idx) break;
      [heap[idx], heap[smallest]] = [heap[smallest], heap[idx]];
      idx = smallest;
    }
  };
  for (const num of nums) {
    heap.push(num);
    bubbleUp(heap.length - 1);
    if (heap.length > k) {
      heap[0] = heap.pop();
      bubbleDown(0);
    }
  }
  return heap[0];
}

Pseudo Code • Sift down (heapify)

Flow Diagram

Swap the root with the last element and remove the last element (this is the extracted value).
Set current index to 0 and loop while it has a child inside bounds.
Pick the smallest (min-heap) or largest (max-heap) child as the swap candidate.
If the candidate violates the heap property, swap and continue bubbling down; otherwise stop.

Heapify runs in O(log n); building a heap from scratch by heapifying bottom-up runs in O(n).

Hands-on code

Compare how the same idea looks in JavaScript, Python, and Go.

class MinHeap {
  constructor() {
    this.data = [];
  }
  insert(value) {
    this.data.push(value);
    this.#bubbleUp(this.data.length - 1);
  }
  extractMin() {
    if (!this.data.length) return null;
    const min = this.data[0];
    const end = this.data.pop();
    if (this.data.length) {
      this.data[0] = end;
      this.#bubbleDown(0);
    }
    return min;
  }
  #bubbleUp(index) {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.data[parent] <= this.data[index]) break;
      [this.data[parent], this.data[index]] = [this.data[index], this.data[parent]];
      index = parent;
    }
  }
  #bubbleDown(index) {
    const length = this.data.length;
    while (true) {
      let left = index * 2 + 1;
      let right = index * 2 + 2;
      let smallest = index;
      if (left < length && this.data[left] < this.data[smallest]) smallest = left;
      if (right < length && this.data[right] < this.data[smallest]) smallest = right;
      if (smallest === index) break;
      [this.data[index], this.data[smallest]] = [this.data[smallest], this.data[index]];
      index = smallest;
    }
  }
}