Heaps

const a = [1, 3, 2, 7, 5, 4]; // a min-heap in an array
const parent = (i: number) => (i - 1) >> 1;
const kids = (i: number) => [2 * i + 1, 2 * i + 2];
parent(5); // 2
kids(1); // [3, 4]
 
// every item is at least its parent
const isMinHeap = (xs: readonly number[]) =>
  xs.every((x, i) => i === 0 || xs[parent(i)]! <= x);
isMinHeap(a); // true
isMinHeap([1, 3, 2, 0]); // false: 0 sits below 3
a.toSorted((x, y) => x - y); // [1, 2, 3, 4, 5, 7]

// A binary heap. cmp(x, y) < 0 puts x nearer the top,
// like sort: (a, b) => a - b is a min-heap.
class Heap<T> {
  private readonly a: T[];
  private readonly cmp: (x: T, y: T) => number;
 
  constructor(
    cmp: (x: T, y: T) => number,
    items: Iterable<T> = [],
  ) {
    this.cmp = cmp;
    this.a = [...items];
    // heapify in O(n): sift down each parent, last first
    for (let i = (this.a.length >> 1) - 1; i >= 0; i--) {
      this.down(i);
    }
  }
 
  get size(): number {
    return this.a.length;
  }
 
  peek(): T | undefined {
    return this.a[0];
  }
 
  push(x: T): void {
    this.a.push(x);
    let i = this.a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1; // parent
      if (!this.less(i, p)) break;
      this.swap(i, p);
      i = p;
    }
  }
 
  pop(): T | undefined {
    const end = this.a.length - 1;
    if (end > 0) this.swap(0, end); // last item to the top
    const top = this.a.pop();
    this.down(0);
    return top;
  }
 
  private down(i: number): void {
    const n = this.a.length;
    for (;;) {
      const l = 2 * i + 1; // left child; right is l + 1
      let m = i; // the smallest of i and its children
      if (l < n && this.less(l, m)) m = l;
      if (l + 1 < n && this.less(l + 1, m)) m = l + 1;
      if (m === i) return;
      this.swap(i, m);
      i = m;
    }
  }
 
  // i and j are always in range, so the casts are safe
  private less(i: number, j: number): boolean {
    return this.cmp(this.a[i] as T, this.a[j] as T) < 0;
  }
 
  private swap(i: number, j: number): void {
    const t = this.a[i] as T;
    this.a[i] = this.a[j] as T;
    this.a[j] = t;
  }
}
 
const h = new Heap<number>((a, b) => a - b, [5, 1, 8, 3]);
h.peek(); // 1
h.push(0);
[h.pop(), h.pop()]; // [0, 1]
h.size; // 3
new Heap<number>((a, b) => a - b).pop(); // undefined

// Heap<T>: the class from A typed heap, above
const maxH = new Heap<number>((a, b) => b - a, [3, 9, 4]);
maxH.pop(); // 9
 
const words = new Heap<string>(
  (a, b) => (a < b ? -1 : a > b ? 1 : 0),
  ["pear", "apple", "fig"],
);
words.pop(); // "apple"
 
type Job = { name: string; cost: number };
const jobs = new Heap<Job>((a, b) => a.cost - b.cost);
jobs.push({ name: "ship", cost: 5 });
jobs.push({ name: "plan", cost: 1 });
jobs.peek()?.name; // "plan"
 
const big = new Heap<bigint>((a, b) =>
  a < b ? -1 : a > b ? 1 : 0,
);
big.push(2n ** 64n);
big.push(1n);
big.pop(); // 1n
// @ts-expect-error: a bigint difference isn't a number
new Heap<bigint>((a, b) => a - b);
 
// NaN compares as neither smaller nor larger: order breaks
const asc = (a: number, b: number) => a - b;
const broken = new Heap<number>(asc, [4, NaN, 2, 1]);
const out: number[] = [];
while (broken.size > 0) out.push(broken.pop()!);
out; // [2, 1, 4, NaN]

// Heap<T>: the class from A typed heap, above
type Pair = [prio: number, name: string];
const plain = new Heap<Pair>((a, b) => a[0] - b[0]);
for (const name of ["a", "b", "c", "d"]) {
  plain.push([1, name]);
}
[1, 2, 3, 4].map(() => plain.pop()?.[1]);
// ["a", "d", "c", "b"]: equal priorities, scrambled
 
type Entry<T> = [prio: number, seq: number, item: T];
const fifo = <T,>(a: Entry<T>, b: Entry<T>) =>
  a[0] - b[0] || a[1] - b[1];
const q = new Heap<Entry<string>>(fifo);
let seq = 0;
const todo = [[2, "b"], [1, "a"], [2, "c"]] as const;
for (const [prio, job] of todo) q.push([prio, seq++, job]);
const order: string[] = [];
while (q.size > 0) order.push(q.pop()![2]);
order; // ["a", "b", "c"]

// Heap<T>: the class from A typed heap, above
const best = new Map([["a", 5], ["b", 3]]); // current prio
const h = new Heap<[number, string]>(
  (x, y) => x[0] - y[0],
  [[5, "a"], [3, "b"]],
);
best.set("a", 1); // decrease-key: record it...
h.push([1, "a"]); // ...and push a fresh entry
const order: [string, number][] = [];
while (h.size > 0) {
  const [prio, key] = h.pop()!;
  if (prio !== best.get(key)) continue; // stale
  order.push([key, prio]);
}
order; // [["a", 1], ["b", 3]]

// Heap<T>: the class from A typed heap, above
function topK(xs: Iterable<number>, k: number): number[] {
  const h = new Heap<number>((a, b) => a - b); // min-heap
  for (const x of xs) {
    if (h.size < k) h.push(x);
    else if (x > h.peek()!) {
      h.pop(); // evict the weakest kept item
      h.push(x);
    }
  }
  const out: number[] = [];
  while (h.size > 0) out.push(h.pop()!);
  return out.reverse(); // largest first
}
topK([5, 1, 9, 3, 7, 9, 2], 3); // [9, 9, 7]
 
function* merge(...lists: number[][]): Generator<number> {
  type Head = [value: number, list: number, index: number];
  const h = new Heap<Head>((a, b) => a[0] - b[0]);
  lists.forEach((xs, i) => {
    if (xs.length > 0) h.push([xs[0]!, i, 0]);
  });
  while (h.size > 0) {
    const [v, i, j] = h.pop()!;
    yield v;
    const xs = lists[i]!;
    if (j + 1 < xs.length) h.push([xs[j + 1]!, i, j + 1]);
  }
}
[...merge([1, 4, 9], [2, 3, 10], [5])];
// [1, 2, 3, 4, 5, 9, 10]

// Heap<T>: the class from A typed heap, above
class Median {
  private lo = new Heap<number>((a, b) => b - a); // max
  private hi = new Heap<number>((a, b) => a - b); // min
 
  add(x: number): void {
    this.lo.push(x);
    this.hi.push(this.lo.pop()!); // lo's largest → hi
    if (this.hi.size > this.lo.size) {
      this.lo.push(this.hi.pop()!);
    }
  }
 
  median(): number {
    const lo = this.lo.peek() ?? NaN;
    if (this.lo.size > this.hi.size) return lo;
    return (lo + (this.hi.peek() ?? NaN)) / 2;
  }
}
 
const m = new Median();
const out: number[] = [];
for (const x of [5, 15, 1, 3]) {
  m.add(x);
  out.push(m.median());
}
out; // [5, 10, 5, 4]

function heapSort(a: number[]): number[] {
  const down = (i: number, n: number): void => {
    for (;;) {
      const l = 2 * i + 1;
      let m = i; // the largest of i and its children
      if (l < n && a[l]! > a[m]!) m = l;
      if (l + 1 < n && a[l + 1]! > a[m]!) m = l + 1;
      if (m === i) return;
      [a[i], a[m]] = [a[m]!, a[i]!];
      i = m;
    }
  };
  for (let i = (a.length >> 1) - 1; i >= 0; i--) {
    down(i, a.length); // a max-heap, in place
  }
  for (let end = a.length - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end]!, a[0]!]; // max to the end
    down(0, end);
  }
  return a;
}
heapSort([5, 2, 9, 1, 5, 6]); // [1, 2, 5, 5, 6, 9]

import {
  MaxPriorityQueue,
  MinPriorityQueue,
  PriorityQueue,
} from "@datastructures-js/priority-queue";
 
const nums = new MinPriorityQueue<number>();
nums.enqueue(5).enqueue(1).enqueue(4); // chainable
nums.front(); // 1
nums.dequeue(); // 1
nums.size(); // 2
 
// the callback returns each item's priority
type Bid = { name: string; value: number };
const bids = new MaxPriorityQueue<Bid>((b) => b.value);
bids.enqueue({ name: "x", value: 3000 });
bids.enqueue({ name: "y", value: 1000 });
bids.dequeue()?.name; // "x"
 
// or a comparator, like sort's
const tasks = new PriorityQueue<[number, string]>(
  (a, b) => a[0] - b[0] || a[1].localeCompare(b[1]),
);
tasks.enqueue([2, "write"]).enqueue([1, "test"]);
tasks.dequeue(); // [1, "test"]
new MinPriorityQueue<number>().dequeue(); // null
 
const q = MinPriorityQueue.fromArray([5, 3, 8, 1]);
q.toArray(); // [1, 3, 5, 8]: a sorted copy
[...q]; // [1, 3, 5, 8]
q.size(); // 0: iterating dequeued everything

// Heap<T>: the class from A typed heap, above
const kth = new Heap<number>((a, b) => a - b);
for (const x of [3, 2, 1, 5, 6, 4]) {
  kth.push(x);
  if (kth.size > 2) kth.pop(); // keep the 2 largest
}
kth.peek(); // 5: the 2nd largest
 
type Pt = [x: number, y: number];
const d2 = ([x, y]: Pt) => x * x + y * y;
const near = new Heap<Pt>((a, b) => d2(b) - d2(a)); // max
const pts: Pt[] = [[1, 3], [-2, 2], [5, 8], [0, 1]];
for (const p of pts) {
  near.push(p);
  if (near.size > 2) near.pop(); // drop the farthest
}
[near.pop(), near.pop()]; // [[-2, 2], [0, 1]]

// Heap<T>: the class from A typed heap, above
type Cmp<T> = (a: T, b: T) => number;
type Entry = readonly [prio: number, name: string];
const byPrio: Cmp<Entry> = (a, b) => a[0] - b[0];
const q = new Heap<Entry>(byPrio, [[2, "b"], [1, "a"]]);
 
const bump = (e: Entry) => {
  // @ts-expect-error: readonly, so the priority can't change
  e[0] = 9;
};
// @ts-expect-error: the comparator must return a number
new Heap<string>((a, b) => a > b);
 
const top = q.pop(); // Entry | undefined
const prio = top?.[0] ?? -1;
prio; // 1

// Heap<T>: the class from A typed heap, above
class KthLargest {
  private readonly h = new Heap<number>((a, b) => a - b);
  private readonly k: number;
 
  constructor(k: number, nums: number[]) {
    this.k = k;
    for (const x of nums) this.add(x);
  }
 
  add(x: number): number {
    this.h.push(x);
    if (this.h.size > this.k) this.h.pop();
    return this.h.peek()!;
  }
}
 
const s = new KthLargest(3, [4, 5, 8, 2]);
[3, 5, 10, 9, 4].map((x) => s.add(x)); // [4, 5, 5, 8, 8]

// Heap<T>: the class from A typed heap, above
function topKFrequent(nums: number[], k: number): number[] {
  const count = new Map<number, number>();
  for (const x of nums) {
    count.set(x, (count.get(x) ?? 0) + 1);
  }
  const h = new Heap<[n: number, x: number]>(
    (a, b) => a[0] - b[0], // min-heap by count
  );
  for (const [x, n] of count) {
    h.push([n, x]);
    if (h.size > k) h.pop();
  }
  const out: number[] = [];
  while (h.size > 0) out.push(h.pop()![1]);
  return out.reverse(); // most frequent first
}
 
topKFrequent([1, 1, 1, 2, 2, 3], 2); // [1, 2]

// Heap<T>: the class from A typed heap, above
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}
const list = (...xs: number[]) =>
  xs.reduceRight<ListNode | null>(
    (next, v) => new ListNode(v, next),
    null,
  );
 
function mergeKLists(lists: (ListNode | null)[]) {
  const h = new Heap<ListNode>((a, b) => a.val - b.val);
  for (const node of lists) if (node) h.push(node);
  const dummy = new ListNode();
  let tail = dummy;
  while (h.size > 0) {
    const node = h.pop()!;
    tail = tail.next = node;
    if (node.next) h.push(node.next);
  }
  return dummy.next;
}
 
const lists = [list(1, 4, 5), list(1, 3, 4), list(2, 6)];
let n = mergeKLists(lists);
const vals: number[] = [];
for (; n; n = n.next) vals.push(n.val);
vals; // [1, 1, 2, 3, 4, 4, 5, 6]

// Heap<T>: the class from A typed heap, above
function minRooms(meetings: [number, number][]): number {
  const sorted = meetings.toSorted((a, b) => a[0] - b[0]);
  const ends = new Heap<number>((a, b) => a - b);
  for (const [start, end] of sorted) {
    if (ends.size > 0 && ends.peek()! <= start) ends.pop();
    ends.push(end); // reuse that room, or open one
  }
  return ends.size;
}
 
minRooms([[0, 30], [5, 10], [15, 20]]); // 2
minRooms([[7, 10], [2, 4]]); // 1

// Heap<T>: the class from A typed heap, above
function leastInterval(tasks: string[], n: number): number {
  const count = new Map<string, number>();
  for (const t of tasks) {
    count.set(t, (count.get(t) ?? 0) + 1);
  }
  const ready = new Heap<number>( // max-heap of counts
    (a, b) => b - a,
    count.values(),
  );
  const cooling: [left: number, at: number][] = []; // FIFO
  let time = 0;
  while (ready.size > 0 || cooling.length > 0) {
    time++;
    const left = (ready.pop() ?? 0) - 1;
    if (left > 0) cooling.push([left, time + n]);
    if (cooling[0]?.[1] === time) {
      ready.push(cooling.shift()![0]); // ready again
    }
  }
  return time;
}
 
leastInterval(["A", "A", "A", "B", "B", "B"], 2); // 8
leastInterval(["A", "C", "A", "B", "D", "B"], 1); // 6

// Heap<T>: the class from A typed heap, above
function reorganize(s: string): string {
  const count = new Map<string, number>();
  for (const ch of s) {
    count.set(ch, (count.get(ch) ?? 0) + 1);
  }
  type Left = [n: number, ch: string];
  const h = new Heap<Left>(
    (a, b) => b[0] - a[0], // max-heap by count
    [...count].map(([ch, n]): Left => [n, ch]),
  );
  const out: string[] = [];
  let held: Left | null = null; // used last round
  while (h.size > 0) {
    const [n, ch] = h.pop()!;
    out.push(ch);
    if (held) h.push(held);
    held = n > 1 ? [n - 1, ch] : null;
  }
  return held ? "" : out.join("");
}
 
reorganize("aab"); // "aba"
reorganize("aaab"); // ""

// Heap<T>: the class from A typed heap, above
function lastStoneWeight(stones: number[]): number {
  const h = new Heap<number>((a, b) => b - a, stones);
  while (h.size > 1) {
    const diff = h.pop()! - h.pop()!;
    if (diff > 0) h.push(diff);
  }
  return h.peek() ?? 0;
}
 
lastStoneWeight([2, 7, 4, 1, 8, 1]); // 1
lastStoneWeight([2, 2]); // 0

// Heap<T>: the class from A typed heap, above
function maxCapital(
  k: number,
  w: number,
  profits: number[],
  capital: number[],
): number {
  const locked = capital
    .map((c, i): [number, number] => [c, profits[i]!])
    .sort((a, b) => a[0] - b[0]); // by cost
  const ready = new Heap<number>((a, b) => b - a); // max
  let i = 0;
  for (let round = 0; round < k; round++) {
    while (i < locked.length && locked[i]![0] <= w) {
      ready.push(locked[i++]![1]);
    }
    if (ready.size === 0) break; // nothing affordable
    w += ready.pop()!;
  }
  return w;
}
 
maxCapital(2, 0, [1, 2, 3], [0, 1, 1]); // 4
maxCapital(3, 0, [1, 2, 3], [0, 1, 2]); // 6

// Heap<T>: the class from A typed heap, above
type Item<K> = {
  prio: number;
  seq: number;
  key: K;
  alive: boolean;
};
 
class UpdatableQueue<K> {
  private readonly h = new Heap<Item<K>>(
    (a, b) => a.prio - b.prio || a.seq - b.seq,
  );
  private readonly live = new Map<K, Item<K>>();
  private seq = 0;
 
  set(key: K, prio: number): void {
    this.delete(key); // update = remove + add
    const item = { prio, seq: this.seq++, key, alive: true };
    this.live.set(key, item);
    this.h.push(item);
  }
 
  delete(key: K): void {
    const item = this.live.get(key);
    if (item) item.alive = false; // lazy: stays inside
    this.live.delete(key);
  }
 
  pop(): K | undefined {
    while (this.h.size > 0) {
      const item = this.h.pop()!;
      if (!item.alive) continue;
      this.live.delete(item.key);
      return item.key;
    }
    return undefined;
  }
}
 
const pq = new UpdatableQueue<string>();
pq.set("write", 3);
pq.set("test", 2);
pq.set("ship", 5);
pq.set("ship", 1); // raise its priority
pq.delete("test");
[pq.pop(), pq.pop(), pq.pop()];
// ["ship", "write", undefined]