Top-K with a Heap - TypeScript DSA

Keep only the largest k values by maintaining a small min-heap.

Algorithm

Steps

Store the heap in an array.
Compare parent and child indexes instead of building explicit tree nodes.
Swap only when the heap order is violated.
Print the deterministic final heap state for replay comparison.

Complexity

Time: O(n log k)
Space: O(k)

bounded heap For top-k largest values, a min-heap of size k keeps the current cutoff at the root.

TypeScript DSA Implementation

basic.ts

function listString(values: number[]): string { return `[${values.join(", ")}]`; }
function heapInsert(heap: number[], value: number): void {
  heap.push(value);
  let child = heap.length - 1;
  while (child > 0) {
    const parent = Math.floor((child - 1) / 2);
    if (heap[parent] <= heap[child]) break;
    [heap[parent], heap[child]] = [heap[child], heap[parent]];
    child = parent;
  }
}
function heapPop(heap: number[]): number {
  const smallest = heap[0];
  heap[0] = heap.pop()!;
  let parent = 0;
  while (true) {
    const left = parent * 2 + 1;
    const right = left + 1;
    if (left >= heap.length) break;
    let child = left;
    if (right < heap.length && heap[right] < heap[left]) child = right;
    if (heap[parent] <= heap[child]) break;
    [heap[parent], heap[child]] = [heap[child], heap[parent]];
    parent = child;
  }
  return smallest;
}
const values: number[] = [5, 1, 9, 3, 7, 2];
const heap: number[] = [];
for (const value of values) { heapInsert(heap, value); if (heap.length > 3) heapPop(heap); }
console.log(listString([...heap].sort((a, b) => b - a)));

Output

[9, 7, 5]

Implementation notes

In TypeScript, both values and heap are explicit number[] arrays: values holds [5, 1, 9, 3, 7, 2], while heap starts empty and is mutated by the helper functions.
The loop uses for (const value of values), calls heapInsert(heap, value) for every number, then calls heapPop(heap) only when heap.length > 3. That keeps a fixed-size min-heap of the current top three values.
heapInsert appends with push, computes parents with Math.floor((child - 1) / 2), and swaps heap slots with destructuring. heapPop uses heap.pop()!, root replacement, child indexes parent * 2 + 1 and left + 1, and the smaller-child comparison.
The trace records top-k heap states after each value: [5], [1, 5], [1, 5, 9], [3, 5, 9], [5, 7, 9], then unchanged [5, 7, 9] after considering 2.
console.log(listString([...heap].sort((a, b) => b - a))) prints [9, 7, 5]. The spread creates a sorted output copy; the helper mutations stay on the bounded heap array.