Priority queues, top-K patterns, merge K sorted lists, and heap implementation from scratch

Heaps

A heap is a complete binary tree where every parent is smaller (min-heap) or larger (max-heap) than its children. It gives you O(1) access to the min/max and O(log n) insertion and removal. Whenever a problem mentions "K largest," "K smallest," "median," or "merge sorted" -- think heap.

How Heaps Work

A heap is stored as an array. For a node at index i:

Left child: 2i + 1
Right child: 2i + 2
Parent: Math.floor((i - 1) / 2)

        1              Array: [1, 3, 2, 7, 4, 5, 6]
       / \
      3   2            Index:  0  1  2  3  4  5  6
     / \ / \
    7  4 5  6

Operations

Operation	Time	Description
peek	O(1)	Return min/max without removing
push	O(log n)	Add element, bubble up
pop	O(log n)	Remove min/max, bubble down
heapify	O(n)	Build heap from array

Implementation

class MinHeap {
  private heap: number[] = [];

  get size(): number {
    return this.heap.length;
  }

  peek(): number {
    return this.heap[0];
  }

  push(val: number): void {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }

  pop(): number {
    const min = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return min;
  }

  private bubbleUp(i: number): void {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

  private bubbleDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;

      if (left < n && this.heap[left] < this.heap[smallest]) smallest = left;
      if (right < n && this.heap[right] < this.heap[smallest]) smallest = right;

      if (smallest === i) break;
      [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
      i = smallest;
    }
  }
}

Pattern 1: Top-K Elements

K Largest Elements: Use a min-heap of size K. The smallest element in the heap is the Kth largest overall.

function topKLargest(nums: number[], k: number): number[] {
  const heap = new MinHeap();

  for (const num of nums) {
    heap.push(num);
    if (heap.size > k) {
      heap.pop(); // remove smallest, keeping K largest
    }
  }

  const result: number[] = [];
  while (heap.size > 0) {
    result.push(heap.pop());
  }
  return result;
}
// Time: O(n log k), Space: O(k)

Why min-heap for K largest? Because we want to evict the smallest of the candidates. The heap root is always the boundary element.

K Closest Points to Origin:

function kClosest(points: number[][], k: number): number[][] {
  // Max-heap by distance (negate to simulate max-heap with min-heap)
  const dist = (p: number[]) => p[0] * p[0] + p[1] * p[1];

  // Sort-based approach (simpler for interviews)
  points.sort((a, b) => dist(a) - dist(b));
  return points.slice(0, k);

  // Heap approach is O(n log k) vs O(n log n) for sort
}

Pattern 2: Kth Largest Element

function findKthLargest(nums: number[], k: number): number {
  const heap = new MinHeap();

  for (const num of nums) {
    heap.push(num);
    if (heap.size > k) {
      heap.pop();
    }
  }

  return heap.peek(); // the smallest in the heap = Kth largest overall
}
// Time: O(n log k)

Alternative: Quickselect gives O(n) average but O(n^2) worst case. The heap approach is more predictable.

Pattern 3: Merge K Sorted Lists

Use a min-heap to always pick the smallest current head across all lists.

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeKSorted(lists: (ListNode | null)[]): ListNode | null {
  // In a real implementation, the heap would store [value, listIndex]
  // Here we show the logic with a simple sorted approach
  const values: number[] = [];

  for (const list of lists) {
    let node = list;
    while (node) {
      values.push(node.val);
      node = node.next;
    }
  }

  values.sort((a, b) => a - b);

  const dummy = new ListNode(0);
  let current = dummy;
  for (const val of values) {
    current.next = new ListNode(val);
    current = current.next;
  }

  return dummy.next;
}
// With heap: O(n log k) where n = total elements, k = number of lists
// With sort: O(n log n)

The heap approach processes one element at a time, always choosing the minimum across K list heads. This is O(n log k) -- better than O(n log n) when k is much smaller than n.

Pattern 4: Median Finder (Two Heaps)

Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half.

class MedianFinder {
  private lo: number[] = [];  // max-heap (store negated values)
  private hi: number[] = [];  // min-heap

  private pushLo(val: number): void {
    // Simulate max-heap by negating
    this.lo.push(-val);
    this.lo.sort((a, b) => a - b); // In production, use proper heap operations
  }

  private pushHi(val: number): void {
    this.hi.push(val);
    this.hi.sort((a, b) => a - b);
  }

  addNum(num: number): void {
    // Always add to max-heap first
    this.pushLo(num);

    // Balance: max of lower half must <= min of upper half
    this.pushHi(-this.lo.shift()!);

    // Keep sizes balanced: lo.length >= hi.length
    if (this.lo.length < this.hi.length) {
      this.pushLo(this.hi.shift()!);
    }
  }

  findMedian(): number {
    if (this.lo.length > this.hi.length) {
      return -this.lo[0];
    }
    return (-this.lo[0] + this.hi[0]) / 2;
  }
}

The invariant:

Max-heap (lo) contains the smaller half
Min-heap (hi) contains the larger half
lo.size >= hi.size >= lo.size - 1
Median is either lo.peek() or average of both peeks

Pattern 5: Task Scheduler

Given tasks with cooldown periods, find minimum time to complete all.

# Python is cleaner here with heapq
import heapq
from collections import Counter

def leastInterval(tasks: list[str], n: int) -> int:
    counts = list(Counter(tasks).values())
    max_heap = [-c for c in counts]  # negate for max-heap
    heapq.heapify(max_heap)

    time = 0
    cooldown = []  # (available_time, count)

    while max_heap or cooldown:
        time += 1
        if max_heap:
            count = heapq.heappop(max_heap) + 1  # do one task
            if count < 0:
                cooldown.append((time + n, count))

        if cooldown and cooldown[0][0] == time:
            heapq.heappush(max_heap, cooldown.pop(0)[1])

    return time

When to Use Heaps

Signal in problem	Heap type
"K largest" or "K most frequent"	Min-heap of size K
"K smallest" or "K closest"	Max-heap of size K
"Median" or "middle element"	Two heaps (max + min)
"Merge K sorted"	Min-heap of K elements
"Process by priority"	Min or max heap
"Schedule tasks"	Max-heap for greedy scheduling

Language Support

TypeScript/JavaScript: No built-in heap. Implement your own or use a library.
Python: heapq module (min-heap only; negate values for max-heap).
Java: PriorityQueue (min-heap by default; pass comparator for max).
C++: priority_queue (max-heap by default).

Key Takeaways

Top-K uses a heap of size K, not size N. This gives O(n log k) instead of O(n log n).
Min-heap for K largest, max-heap for K smallest. The heap holds what you want to keep, and the root is the eviction candidate.
Two-heap pattern solves median and partition problems. Keep halves balanced.
Heapify is O(n), not O(n log n). Building a heap from an array is cheaper than inserting one by one.
In interviews, state that you would use a heap and describe the API. Most interviewers will not ask you to implement the heap itself.

Heaps

On this page