TS heap implementation

heap.ts

/**
TS heap implementation for use during coding interviews.

Sources:
https://stackfull.dev/heaps-in-javascript - bug in heapify function, needs to run in reverse
https://github.com/ignlg/heap-js/blob/c6bce4c1a3b1cc17d9494731dc2a598e86f67a24/src/Heap.ts
https://dandkim.com/js-heap-implementation/
CPython `heapq` stdlib: https://github.com/python/cpython/blob/3.13/Lib/heapq.py
*/

/**
Heapify an existing array in place. Starting with the last node that has children,
ensure that the subtree is a heap.
*/
function heapify(arr: number[]) {
  for (let i = Math.floor(arr.length / 2); i >= 0; i--) {
    percolateDown(arr, i);
  }
}

/**
Given an array with a subtree starting at `index`, where the subtree is a heap with
the exception of the root, swap nodes in the tree downwards starting with the root,
in order to reconstruct the subtree as a valid heap.
*/
function percolateDown(arr: number[], index: number) {
  let curr = index;
  while (curr < Math.floor(arr.length / 2)) {
    // Find smaller child
    const leftIndex = 2 * curr + 1;
    const rightIndex = leftIndex + 1;
    const minChildIndex =
      rightIndex < arr.length && arr[rightIndex] < arr[leftIndex]
        ? rightIndex
        : leftIndex;

    // Stop if heap property is satisfied
    if (arr[curr] <= arr[minChildIndex]) break;

    // Swap current with smaller child, then repeat for newly-replaced child
    swap(arr, curr, minChildIndex);
    curr = minChildIndex;
  }
}

/**
Add an element to a heap. Inserts the element at the end of the array, and then
swap upward with its parent until it reaches a valid location in the heap.
*/
function heappush(heap: number[], value: number) {
  heap.push(value);

  let curr = heap.length - 1;
  while (curr > 0) {
    let parent = Math.floor((curr - 1) / 2);
    if (heap[parent] <= heap[curr]) break;
    swap(heap, curr, parent);
    curr = parent;
  }
}

/**
Remove the first element and reconstruct the heap.
*/
function heappop(heap: number[]) {
  swap(heap, 0, heap.length - 1);
  const removed = heap.pop();
  percolateDown(heap, 0);
  return removed;
}

/**
Helper function to swap 2 elements in an array.
*/
function swap(arr: number[], first: number, second: number) {
  const temp = arr[first];
  arr[first] = arr[second];
  arr[second] = temp;
}

const input = [115, 51, 31, 16, 100, 41, 13];
heapify(input);
console.log(input);

heappush(input, 99);
console.log(input);

console.log(heappop(input));
console.log(input);