Algorithms & Coding Interviews · Recursion & Trees

Heaps & Top-K

Heaps give the best remaining item in O(1) and update in O(log n). Learn heaps in Python, TypeScript (write your own) and C#, the four heap patterns (top-k, k-way merge, two heaps, greedy), how the array layout works, and watch a size-k heap and a running median animated.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 17 min read▶ 2 interactive🛠️ 4 exercises

🎯 What you'll learn

Priority queues per language, including a TS MinHeap
Top-k with a size-k min-heap
k-way merge, two heaps for medians, greedy scheduling
Six LeetCode problems up to Find Median from Data Stream

📚 Before you start

Part 1The Pattern

A heap (priority queue) gives you the smallest (or largest) element in O(1) and inserts or removes in O(log n). Reach for one whenever you repeatedly need "the best remaining item": top-k elements, merging k sorted streams, scheduling by priority, running medians, and Dijkstra's shortest paths.

A min-heap stored in an array: children of i live at 2i+1 and 2i+2

1Heaps in Each Language

	Python	TypeScript / JavaScript	C#
type	`heapq` functions on a list (min-heap)	no built-in: write a small class (below)	`PriorityQueue<TElement, TPriority>` (min by priority)
push / pop	`heappush(h, x)`, `heappop(h)`	`heap.push(x)`, `heap.pop()`	`pq.Enqueue(x, p)`, `pq.Dequeue()`
peek	`h[0]`	`heap.peek()`	`pq.Peek()`
build from list	`heapify(list)` O(n)	push each, O(n log n)	`new PriorityQueue<,>(items)`
max-heap	push `-x` (or `(-priority, item)`)	pass a `greater` comparator	negate the priority, or a custom `IComparer`
tuples	`(priority, tiebreak, item)`	comparator on objects	priority type with a comparer

In a JS/TS interview, say "JavaScript has no built-in heap, so I'll write a short one" and implement push with sift up and pop with sift down: about 25 lines, and interviewers expect you to be able to.

2Templates

typescript

class MinHeap<T> {
  private a: T[] = [];
  private less: (x: T, y: T) => boolean;
  constructor(less: (x: T, y: T) => boolean = (x: any, y: any) => x < y) { this.less = less; }
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }
  push(x: T): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a; if (!a.length) return undefined;
    const top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

function kLargest(nums: number[], k: number): number[] {
  const heap = new MinHeap<number>();          // min-heap of the k largest so far
  for (const x of nums) {
    heap.push(x);
    if (heap.size > k) heap.pop();
  }
  const out: number[] = [];
  while (heap.size) out.push(heap.pop()!);
  return out.reverse();
}

python

import heapq

def k_largest(nums, k):
    heap = []                                   # min-heap of the k largest so far
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)                 # drop the smallest
    return sorted(heap, reverse=True)

# max-heap in Python: push negated values
def max_heap_demo(nums):
    h = [-x for x in nums]
    heapq.heapify(h)                            # O(n)
    return -h[0]

3The Four Heap Patterns

Pattern	Idea	Complexity
Top-k / k-th largest	keep a min-heap of size k; pop when it grows past k. The root is the k-th largest	O(n log k)
k-way merge	push the head of each list; pop the smallest, push its successor	O(N log k)
Two heaps	max-heap for the lower half, min-heap for the upper half; balance sizes	O(log n) insert, O(1) median
Greedy by priority	always process the most urgent/frequent/cheapest item next	O(n log n)

Why a min-heap for the k largest? Its root is the smallest of the current top k, exactly the element to evict when something bigger arrives.

4Heap vs Sorting vs Quickselect

Sort once: O(n log n), simplest when you need everything in order.
Heap of size k: O(n log k) with O(k) memory, and works on streams (data arriving over time).
Quickselect: O(n) average for a single k-th element, O(n²) worst case, modifies the array.

Under the HoodThe Array Layout▾

A binary heap is a complete binary tree stored in an array: node i has children at 2i + 1 and 2i + 2 and its parent at (i − 1) // 2. Push appends at the end and sifts up (swap with the parent while smaller): O(log n). Pop moves the last element to the root and sifts down (swap with the smaller child): O(log n). Heapify sifts down every non-leaf from the bottom up, which totals O(n) because most nodes are near the bottom and sift only a little. No pointers and great cache locality: that's why heaps are arrays, not node objects.

⚠️ Common Pitfalls

Using a max-heap of all n elements for top-k: O(n log n) and O(n) memory instead of O(n log k).
Forgetting Python's heapq is a min-heap; negate for max-heap behaviour.
Comparing tuples with uncomparable items ((priority, dict) with equal priorities fails in Python): add a tiebreak counter.
JS default comparator mistakes in a hand-written heap (compare numbers, not strings).
Unbalanced two heaps: keep sizes within one after every insertion.

📋 Quick Reference

text

top-k largest: min-heap; push x; if size > k: pop → root = k-th largest
k-way merge: push (head, list); pop min; push next from same list
median: lo = max-heap (negated), hi = min-heap; |size diff| ≤ 1
children 2i+1, 2i+2 · parent (i-1)//2 · push/pop O(log n) · heapify O(n)

Part 2Interview Problems

Six problems covering the four heap patterns: top-k, simulation, k-way merge, two heaps, and greedy by frequency.

1Kth Largest Element in an Array (LeetCode 215)

🟠 Medium. Return the k-th largest element (in sorted order, not distinct) without fully sorting.

text

nums = [3,2,1,5,6,4], k = 2 → 5

Approach. Keep a min-heap of size k. After processing all numbers, its root is the k-th largest. (Quickselect gives O(n) average if asked.)

Complexity. O(n log k) time, O(k) space.

typescript

class MinHeap<T> {
  private a: T[] = [];
  private less: (x: T, y: T) => boolean;
  constructor(less: (x: T, y: T) => boolean = (x: any, y: any) => x < y) { this.less = less; }
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }
  push(x: T): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a; if (!a.length) return undefined;
    const top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

function findKthLargest(nums: number[], k: number): number {
  const heap = new MinHeap<number>();
  for (const x of nums) {
    heap.push(x);
    if (heap.size > k) heap.pop();
  }
  return heap.peek()!;
}

python

import heapq

def find_kth_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

2Last Stone Weight (LeetCode 1046)

🟢 Easy. Repeatedly smash the two heaviest stones: equal stones both vanish, otherwise the difference remains. Return the last stone's weight (0 if none).

text

[2,7,4,1,8,1] → 1

Approach. Max-heap simulation: pop the two largest, push their difference if non-zero.

Complexity. O(n log n) time.

typescript

class MinHeap<T> {
  private a: T[] = [];
  private less: (x: T, y: T) => boolean;
  constructor(less: (x: T, y: T) => boolean = (x: any, y: any) => x < y) { this.less = less; }
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }
  push(x: T): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a; if (!a.length) return undefined;
    const top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

function lastStoneWeight(stones: number[]): number {
  const heap = new MinHeap<number>((x, y) => x > y);   // max-heap via comparator
  for (const s of stones) heap.push(s);
  while (heap.size > 1) {
    const a = heap.pop()!, b = heap.pop()!;
    if (a !== b) heap.push(a - b);
  }
  return heap.peek() ?? 0;
}

python

import heapq

def last_stone_weight(stones):
    h = [-s for s in stones]
    heapq.heapify(h)
    while len(h) > 1:
        a, b = -heapq.heappop(h), -heapq.heappop(h)
        if a != b:
            heapq.heappush(h, -(a - b))
    return -h[0] if h else 0

3K Closest Points to Origin (LeetCode 973)

🟠 Medium. Return the k points closest to (0, 0). Any order.

text

points = [[3,3],[5,-1],[-2,4]], k = 2 → [[3,3],[-2,4]]

Approach. Max-heap of size k keyed by squared distance (no square root needed): push each point; if the heap exceeds k, pop the farthest.

Complexity. O(n log k) time, O(k) space.

typescript

class MinHeap<T> {
  private a: T[] = [];
  private less: (x: T, y: T) => boolean;
  constructor(less: (x: T, y: T) => boolean = (x: any, y: any) => x < y) { this.less = less; }
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }
  push(x: T): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a; if (!a.length) return undefined;
    const top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

function kClosest(points: number[][], k: number): number[][] {
  const d = (p: number[]) => p[0] * p[0] + p[1] * p[1];
  const heap = new MinHeap<number[]>((a, b) => d(a) > d(b));   // farthest on top
  for (const p of points) {
    heap.push(p);
    if (heap.size > k) heap.pop();
  }
  const out: number[][] = [];
  while (heap.size) out.push(heap.pop()!);
  return out;
}

python

import heapq

def k_closest(points, k):
    heap = []                                   # (-dist, x, y): a max-heap by distance
    for x, y in points:
        heapq.heappush(heap, (-(x * x + y * y), x, y))
        if len(heap) > k:
            heapq.heappop(heap)
    return [[x, y] for _, x, y in heap]

4Merge k Sorted Lists (LeetCode 23)

🔴 Hard. Merge k sorted linked lists into one sorted list.

text

[[1,4,5],[1,3,4],[2,6]] → [1,1,2,3,4,4,5,6]

Approach. Push the head of every non-empty list into a min-heap (by value, with an index tiebreak). Pop the smallest, append it to the result, and push that node's successor.

Complexity. O(N log k) time for N total nodes, O(k) heap space.

typescript

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}
function _build(vals: number[]): ListNode | null {
  const dummy = new ListNode(); let cur = dummy;
  for (const v of vals) { cur.next = new ListNode(v); cur = cur.next; }
  return dummy.next;
}
function _toList(node: ListNode | null): number[] {
  const out: number[] = [];
  while (node) { out.push(node.val); node = node.next; }
  return out;
}

class MinHeap<T> {
  private a: T[] = [];
  private less: (x: T, y: T) => boolean;
  constructor(less: (x: T, y: T) => boolean = (x: any, y: any) => x < y) { this.less = less; }
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }
  push(x: T): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a; if (!a.length) return undefined;
    const top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  const heap = new MinHeap<ListNode>((a, b) => a.val < b.val);
  for (const node of lists) if (node) heap.push(node);
  const dummy = new ListNode(); let tail = dummy;
  while (heap.size) {
    const node = heap.pop()!;
    tail.next = node; tail = node;
    if (node.next) heap.push(node.next);
  }
  return dummy.next;
}

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def _build(vals):
    dummy = cur = ListNode()
    for v in vals:
        cur.next = ListNode(v); cur = cur.next
    return dummy.next

def _to_list(node):
    out = []
    while node:
        out.append(node.val); node = node.next
    return out

import heapq

def merge_k_lists(lists):
    heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
    heapq.heapify(heap)
    dummy = tail = ListNode()
    while heap:
        val, i, node = heapq.heappop(heap)          # i breaks ties (nodes aren't comparable)
        tail.next = node; tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

5Find Median from Data Stream (LeetCode 295)

🔴 Hard. Design addNum(num) and findMedian() for a stream of numbers.

text

addNum(1), addNum(2), findMedian() → 1.5, addNum(3), findMedian() → 2

Approach. Two heaps: a max-heap lo for the smaller half and a min-heap hi for the larger half. Push into lo, move its max to hi (keeps every lo ≤ every hi), then rebalance so lo has at most one extra element. The median is lo's top, or the average of both tops.

Complexity. O(log n) per add, O(1) per median.

typescript

class MinHeap<T> {
  private a: T[] = [];
  private less: (x: T, y: T) => boolean;
  constructor(less: (x: T, y: T) => boolean = (x: any, y: any) => x < y) { this.less = less; }
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }
  push(x: T): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a; if (!a.length) return undefined;
    const top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

class MedianFinder {
  private lo = new MinHeap<number>((a, b) => a > b);   // max-heap: smaller half
  private hi = new MinHeap<number>();                   // min-heap: larger half
  addNum(num: number): void {
    this.lo.push(num);
    this.hi.push(this.lo.pop()!);
    if (this.hi.size > this.lo.size) this.lo.push(this.hi.pop()!);
  }
  findMedian(): number {
    return this.lo.size > this.hi.size ? this.lo.peek()! : (this.lo.peek()! + this.hi.peek()!) / 2;
  }
}

python

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []        # max-heap (negated): smaller half
        self.hi = []        # min-heap: larger half

    def add_num(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))      # move lo's max to hi
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))  # keep lo the bigger half

    def find_median(self):
        if len(self.lo) > len(self.hi):
            return float(-self.lo[0])
        return (-self.lo[0] + self.hi[0]) / 2

6Reorganize String (LeetCode 767)

🟠 Medium. Rearrange s so no two adjacent characters are equal; return any valid arrangement or "" if impossible.

text

"aab" → "aba" · "aaab" → ""

Approach. Greedy with a max-heap by remaining count: repeatedly take the most frequent character that differs from the one just placed (hold the previous character out of the heap for one step). Impossible exactly when some count exceeds (n + 1) / 2.

Complexity. O(n log 26) = O(n) time.

typescript

class MinHeap<T> {
  private a: T[] = [];
  private less: (x: T, y: T) => boolean;
  constructor(less: (x: T, y: T) => boolean = (x: any, y: any) => x < y) { this.less = less; }
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }
  push(x: T): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a; if (!a.length) return undefined;
    const top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

function reorganizeString(s: string): string {
  const counts = new Map<string, number>();
  for (const c of s) counts.set(c, (counts.get(c) ?? 0) + 1);
  const heap = new MinHeap<[number, string]>((a, b) => a[0] > b[0]);   // max by count
  for (const [c, n] of counts) heap.push([n, c]);
  const out: string[] = [];
  let prev: [number, string] | null = null;
  while (heap.size) {
    const [n, c] = heap.pop()!;
    out.push(c);
    if (prev && prev[0] > 0) heap.push(prev);
    prev = [n - 1, c];
  }
  return out.length === s.length ? out.join("") : "";
}

python

import heapq

def reorganize_string(s):
    counts = {}
    for c in s:
        counts[c] = counts.get(c, 0) + 1
    heap = [(-n, c) for c, n in counts.items()]
    heapq.heapify(heap)
    out, prev = [], None                       # prev = (negcount, char) waiting to re-enter
    while heap:
        n, c = heapq.heappop(heap)
        out.append(c)
        if prev and prev[0] < 0:
            heapq.heappush(heap, prev)
        prev = (n + 1, c)                      # one fewer of c remaining
    return "".join(out) if len(out) == len(s) else ""

🧠 Key takeaways

Heap = O(1) peek, O(log n) push/pop; Python heapq is a min-heap, JS has none, C# has PriorityQueue.
Top-k largest → min-heap of size k: O(n log k), works on streams.
k-way merge, two heaps (median) and greedy by priority cover most heap problems.
Array layout: children at 2i+1, 2i+2; heapify is O(n).

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_heaps_and_top_k_exercise_1.py

TS PY

algo_heaps_and_top_k_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. To find the 10 largest of a million numbers, keep…

Evict the smallest of the top 10.

2. How do you get a max-heap from Python's heapq?

Negate.

3. In the two-heap median, the max-heap holds…

Tops meet in the middle.

4. Complexity of heapify on n elements?

Most nodes sift very little.

Source: algo_heaps_and_top_k_theory_1.md, algo_heaps_and_top_k_theory_2.md · generated by tools/build_lessons.py