Overview

Covered the heap data structure end-to-end: array representation, sift-up/sift-down mechanics, O(n) heapify, and a generic TypeScript implementation. Applied to Meeting Rooms II (greedy scheduling) and Find Median from Data Stream (two-heap design). Finished with a 5-problem lightning round to calibrate heap recognition vs. heap-adjacent patterns (monotonic deque, quickselect).

Concept

A min-heap is a complete binary tree where every node ≤ its children. The minimum is always at the root.

Array representation

Because a heap is a complete binary tree, it fits in a flat array with no pointers:

For node at index i (0-indexed):
  parent:      floor((i - 1) / 2)
  left child:  2i + 1
  right child: 2i + 2

Operations

Why heapify is O(n): Most nodes are near the bottom and barely move. Summing the work across levels gives n × Σ k/2^(k+1), which converges to 2n.

Internal nodes are indices 0 through floor(n/2) - 1. Leaves are the back half — already trivially valid heaps. Heapify skips them.

When to reach for a heap

• K smallest/largest elements
• Streaming min/max (running median, merge k sorted lists)
• Greedy scheduling (always process the “best next” item)

Implementation

James wrote a generic Heap<T> with a comparator. Key bugs caught and fixed:

1. extractMin was missing this.#values.pop() — heap grew forever
2. siftDown checked children independently — must pick the smaller child, not just the first

type Comparator<T> = (t: T, u: T) => number

export class Heap<T> {
  readonly #values: Array<T>
  readonly #cmp: Comparator<T>

  constructor(values: Array<T>, cmp: Comparator<T>) {
    this.#values = [...values]
    this.#cmp = cmp
    this.#heapify()
  }

  get size() { return this.#values.length }

  peek() { return this.#values[0] }

  insert(t: T) {
    this.#siftUp(this.#values.push(t) - 1)
  }

  extractMin() {
    if (this.#values.length === 0) return undefined
    const result = this.#values[0]
    this.#values[0] = this.#values.at(-1) as T
    this.#values.pop()           // ← critical: remove the duplicate
    this.#siftDown(0)
    return result
  }

  #heapify() {
    for (let i = Math.floor(this.#values.length / 2) - 1; i >= 0; --i) {
      this.#siftDown(i)
    }
  }

  #siftUp(i: number) {
    const j = Math.floor((i - 1) / 2)
    if (this.#conditionalSwap(i, j)) this.#siftUp(j)
  }

  // Must pick the SMALLER child — not just the first available
  #siftDown(i: number) {
    const left = i * 2 + 1
    const right = i * 2 + 2
    let smallest = i

    if (left < this.#values.length && this.#cmp(this.#values[left], this.#values[smallest]) < 0)
      smallest = left
    if (right < this.#values.length && this.#cmp(this.#values[right], this.#values[smallest]) < 0)
      smallest = right

    if (smallest !== i) {
      const tmp = this.#values[i]
      this.#values[i] = this.#values[smallest]
      this.#values[smallest] = tmp
      this.#siftDown(smallest)
    }
  }

  #conditionalSwap(i: number, j: number): boolean {
    if (i >= this.#values.length || j >= this.#values.length) return false
    if (this.#cmp(this.#values[i], this.#values[j]) >= 0) return false
    const tmp = this.#values[i]
    this.#values[i] = this.#values[j]
    this.#values[j] = tmp
    return true
  }
}

Problems

Meeting Rooms II

Problem: Given an array of meeting intervals [start, end], find the minimum number of conference rooms required.

Approach: Sort by start time. Maintain a min-heap of room end times. For each meeting: if the earliest-ending room frees up before the meeting starts (heap.peek() <= meeting.start), reuse it (extract + insert new end time). Otherwise open a new room (insert new end time). Answer is heap.size.

Key mental model: each heap entry = one room’s current end time. The heap always tells you which room frees up soonest.

Solution:

import { Heap, type Comparator } from './Heap'

type Interval = [number, number]
const BY_END: Comparator<Interval> = (a, b) => a[1] - b[1]

export function roomCount(intervals: Interval[]): number {
  if (intervals.length === 0) return 0

  const sorted = intervals.toSorted((a, b) => a[0] - b[0])  // sort by start (numeric!)
  const [first, ...rest] = sorted
  const rooms = new Heap<Interval>([first], BY_END)

  for (const meeting of rest) {
    if (rooms.peek()[1] > meeting[0]) {
      rooms.insert(meeting)          // no room free → new room
    } else {
      rooms.extractMin()
      rooms.insert(meeting)          // reuse earliest-ending room
    }
  }

  return rooms.size
}

Bugs James caught mid-implementation:

• toSorted() without a comparator sorts as strings — wrong for multi-digit numbers
• Condition was comparing end times instead of checking room.end <= meeting.start
• rooms.size required adding a get size() to the Heap class

Find Median from Data Stream

Problem: Design a structure supporting addNum(num) and findMedian() in O(log n) / O(1).

Approach: Two heaps:

• lower: max-heap of the smaller half (size = ⌈n/2⌉)
• upper: min-heap of the larger half (size = ⌊n/2⌋)

Invariant: lower.size === upper.size or lower.size === upper.size + 1.

addNum(num):
  if lower is empty or num < lower.peek():
    lower.insert(num)
    if lower.size > upper.size + 1:
      upper.insert(lower.extractMin())   // rebalance
  else:
    upper.insert(num)
    if lower.size < upper.size:
      lower.insert(upper.extractMin())   // rebalance

findMedian():
  if lower.size > upper.size:
    return lower.peek()
  else:
    return (lower.peek() + upper.peek()) / 2

Max-heap for lower: flip the comparator sign — new Heap([], (a, b) => b - a).

Lightning Round — Pattern Recognition

Key takeaways:

• Sliding window maximum → deque, not heap
• K closest → heap of size k or quickselect; distances don’t slide monotonically