Heaps Operations & Functions

Heap functions

Each snippet below is something you will reach for while solving priority-queue problems. Skim the short description, then copy the patterns for common situations.

Prefer Overview for how heaps work, and Problems for practice once problems are linked.

Index helpers

Parent and child positions are pure arithmetic on the array. Memorize these three.

parent()

Returns the parent index of i. Root has no parent — guard i > 0 before calling.

parent.tsTypeScript

function parent(i: number): number {
  return Math.floor((i - 1) / 2);
}

// ——— examples ———
parent(1); // 0
parent(2); // 0
parent(5); // 2

left() / right()

Returns the left and right child indexes. Check against heap.length before reading.

children.tsTypeScript

function left(i: number): number {
  return 2 * i + 1;
}

function right(i: number): number {
  return 2 * i + 2;
}

// ——— examples ———
left(0); // 1
right(0); // 2
left(1); // 3

swap()

Exchange two slots. Used by every sift step.

swap.tsTypeScript

function swap(heap: number[], a: number, b: number): void {
  const tmp = heap[a]!;
  heap[a] = heap[b]!;
  heap[b] = tmp;
}

Push + sift-up

Append at the end, then bubble toward the root while the child outranks its parent.

siftUp()

Walk from i toward the root, swapping while heap[i] is better than its parent.

sift-up.tsTypeScript

function siftUp(heap: number[], i: number): void {
  while (i > 0) {
    const p = Math.floor((i - 1) / 2);
    if (heap[i]! >= heap[p]!) break; // min-heap
    swap(heap, i, p);
    i = p;
  }
}

push()

Add a value in O(log n). Append, then sift up.

push.tsTypeScript

function push(heap: number[], value: number): void {
  heap.push(value);
  siftUp(heap, heap.length - 1);
}

const heap: number[] = [];
push(heap, 5);
push(heap, 2);
push(heap, 9);
// heap[0] === 2

Peek, size & empty

The root is always index 0. Reading it never moves anything.

peek()

Returns the current best value, or undefined when the heap is empty.

peek.tsTypeScript

function peek(heap: number[]): number | undefined {
  return heap[0];
}

const heap = [2, 5, 3];
peek(heap); // 2

size() / isEmpty()

Length checks you will use before every pop.

size.tsTypeScript

function size(heap: number[]): number {
  return heap.length;
}

function isEmpty(heap: number[]): boolean {
  return heap.length === 0;
}

Pop + sift-down

Remove the root, park the last value in its place, then slide that value down.

siftDown()

From i, repeatedly swap with the better child until the invariant holds.

sift-down.tsTypeScript

function siftDown(heap: number[], i: number): void {
  const n = heap.length;
  while (true) {
    const l = 2 * i + 1;
    const r = 2 * i + 2;
    let best = i;
    if (l < n && heap[l]! < heap[best]!) best = l;
    if (r < n && heap[r]! < heap[best]!) best = r;
    if (best === i) break;
    swap(heap, i, best);
    i = best;
  }
}

pop()

Extract-min (or max). O(log n). Returns undefined on an empty heap.

pop.tsTypeScript

function pop(heap: number[]): number | undefined {
  if (heap.length === 0) return undefined;
  if (heap.length === 1) return heap.pop();

  const best = heap[0]!;
  heap[0] = heap.pop()!;
  siftDown(heap, 0);
  return best;
}

Heapify

Build a heap from an unordered array in O(n) by sifting parents bottom-up.

heapify()

Mutates the array in place into a valid min-heap.

heapify.tsTypeScript

function heapify(heap: number[]): void {
  const n = heap.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(heap, i);
  }
}

const a = [9, 5, 3, 2, 7];
heapify(a);
// a[0] is the minimum

fromArray()

Copy then heapify when you must not mutate the input.

from-array.tsTypeScript

function fromArray(values: readonly number[]): number[] {
  const heap = values.slice();
  heapify(heap);
  return heap;
}

Top-K pattern

Keep a bounded heap of size k. For “k largest,” use a min-heap of the winners so far.

kLargest()

Stream values; if the heap is full and the next value beats the root, replace and sift.

k-largest.tsTypeScript

function kLargest(nums: number[], k: number): number[] {
  const heap: number[] = [];
  for (const v of nums) {
    if (heap.length < k) {
      push(heap, v); // min-heap of current top-k
      continue;
    }
    if (v > heap[0]!) {
      heap[0] = v;
      siftDown(heap, 0);
    }
  }
  return heap.sort((a, b) => b - a);
}

kSmallest()

Same idea with a max-heap of size k (compare flipped).

k-smallest.tsTypeScript

function kSmallest(nums: number[], k: number): number[] {
  // Max-heap of size k: root is the largest among the small ones.
  const heap: number[] = [];
  for (const v of nums) {
    if (heap.length < k) {
      pushMax(heap, v);
      continue;
    }
    if (v < heap[0]!) {
      heap[0] = v;
      siftDownMax(heap, 0);
    }
  }
  return heap.sort((a, b) => a - b);
}

Priority queue uses

Heaps power Dijkstra, merge-k-lists, and any “always take the next best” loop.

Dijkstra frontier

Store [distance, node] pairs; pop the smallest distance each step. (Sketch — wire your graph types.)

dijkstra-pq.tsTypeScript

type Edge = { to: number; weight: number };

// Min-heap of [dist, node]
function dijkstraSketch(graph: Edge[][], start: number): number[] {
  const dist = graph.map(() => Infinity);
  dist[start] = 0;
  const pq: number[][] = [[0, start]]; // heapify by dist

  while (pq.length > 0) {
    const [d, u] = popPair(pq)!;
    if (d !== dist[u]) continue; // stale entry
    for (const { to, weight } of graph[u]!) {
      const nd = d + weight;
      if (nd < dist[to]!) {
        dist[to] = nd;
        pushPair(pq, [nd, to]);
      }
    }
  }
  return dist;
}

Typed MinHeap class

Wrap the helpers when a problem wants a reusable priority queue.

min-heap-class.tsTypeScript

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

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

  peek(): number | undefined {
    return this.data[0];
  }

  push(value: number): void {
    push(this.data, value);
  }

  pop(): number | undefined {
    return pop(this.data);
  }
}

Heaps