heapSort

heap-sort.js

/**
 * "If a is less than b, return 1, else if b is less than a, return -1, else return 0."
 * 
 * The above function is a comparator function. It's used to compare two values. It's used by the
 * sort() method to determine the order of the elements in the array
 * @param {T} a - The first value to compare.
 * @param {T} b - The second value to compare.
 * @returns A function that takes two arguments and returns a number.
 */
function maxHeap<T>(a: T, b: T): number {
  if (a < b) {
    return 1;
  } 
  else if (b < a) {
    return -1;
  }

  return 0;
}

/**
 * If the left or right child of the current node is smaller than the current node, swap the current
 * node with the smaller child
 * @param {T[]} arr - The array to sort
 * @param {number} index - the index of the element to sift down
 * @param {number} size - the size of the heap
 * @param comparator - a function that takes two elements and returns a number.
 */
function siftDown<T>(
  arr: T[], 
  index: number, 
  size: number,
  comparator = maxHeap
): void {
  const left = 2 * index + 1;
  const right = 2 * index + 2;

  let curr = index;

  if (left < size && comparator(arr[curr], arr[left]) > 0) {
    curr = left;
  }
  if (right < size && comparator(arr[curr], arr[right]) > 0) {
    curr = right;
  }

  if (curr !== index) {
    [ arr[curr], arr[index] ] = [ arr[index], arr[curr] ];
    siftDown(arr, curr, size, comparator);
  }
}

/**
 * We start by building a max heap from the array, then we swap the first element with the last
 * element, and then we sift down the first element to its correct position
 * @param {T[]} arr - The array to sort.
 * @param comparator - a function that takes two arguments and returns a number.
 * @returns The sorted array.
 */
export function heapSort<T>(
  arr: T[], 
  comparator = maxHeap
): T[] {
  let n = arr.length;
  const lastParent = Math.floor((n - 2) / 2);
  for (let i = 0; i <= lastParent; i++) {
    siftDown(arr, i, n, comparator);
  }

  while (--n) {
    [ arr[0], arr[n] ] = [ arr[n], arr[0] ];
    siftDown(arr, 0, n, comparator);
  }

  return arr;
}