Heapsort

A sorting technique that uses a binary heap, first building a max-heap and then repeatedly extracting the maximum element, ensuring efficient sorting.

/**
 * @file Finite Automata
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 * @see Computer Science and Artificial Intelligence Laboratory, MIT.
 *   {@link Heap Algorithms|https://courses.csail.mit.edu/6.006/fall10/handouts/recitation10-8.pdf}
 */

class Heap {
  constructor(
    public heap: number[],
    public heapSize = 0,
  ) {}

get length() {
    return this.heap.length;
  }

toString() {
    return this.heap.toString();
  }
}

/**
 * Computes the parent index for a given index in a heap.
 *
 * @param parentIndex - The current index in the heap.
 * @returns The parent index or undefined if the given index is the root.
 */
function computeParentIndex(parentIndex: number): number | undefined {
  if (parentIndex === 1) {
    return undefined;
  }

return Math.floor(parentIndex / 2);
}

/**
 * Computes the left child index for a given index in a heap.
 *
 * @param heapArray - The heap array.
 * @param currentIndex - The current index in the heap.
 * @returns The left child index or undefined if no left child exists.
 */
function computeLeftChildIndex(
  heapArray: Heap,
  currentIndex: number,
): number | undefined {
  if (2 * currentIndex <= heapArray.heapSize) {
    return 2 * currentIndex;
  }

return undefined;
}

/**
 * Computes the right child index for a given index in a heap.
 *
 * @param heapArray - The heap array.
 * @param currentIndex - The current index in the heap.
 * @returns The right child index or undefined if no right child exists.
 */
function computeRightChildIndex(
  heapArray: Heap,
  currentIndex: number,
): number | undefined {
  if (2 * currentIndex + 1 <= heapArray.heapSize) {
    return 2 * currentIndex + 1;
  }

return undefined;
}

/**
 * Swaps two elements in a heap.
 *
 * @param heapArray - The heap array.
 * @param firstElementIndex - The index of the first element.
 * @param j - The index of the second element.
 */
function exchangeHeapElements(
  heapArray: Heap,
  firstElementIndex: number,
  secondElementIndex: number,
): void {
  const temporary = heapArray.heap[firstElementIndex];
  heapArray.heap[firstElementIndex] = heapArray.heap[secondElementIndex];
  heapArray.heap[secondElementIndex] = temporary;
}

/**
 * Retrieves the maximum value from the heap.
 *
 * @param heapArray - The heap array.
 * @returns The maximum value at the root of the heap.
 */
function getHeapMaximum(heapArray: Heap): number {
  return heapArray.heap[0];
}

/**
 * Extracts and returns the maximum element from the heap, and rebalances the
 * heap.
 *
 * @param heapArray - The heap array.
 * @returns The maximum value from the heap.
 * @throws If the heap size is less than 1, indicating a heap underflow.
 */
function heapExtractMax(heapArray: Heap): number {
  if (!heapArray.heapSize) throw new Error('Missing heapSize');
  if (heapArray.heapSize < 1) {
    throw new Error('heap underflow');
  }

const max = heapArray.heap[0];
  heapArray.heap[0] = heapArray.heap.pop() ?? 0;
  heapArray.heapSize--;
  maxHeapify(heapArray, 0);
  return max;
}

/**
 * Increases the key at a given index in the heap and adjusts the heap to
 * maintain the heap property.
 *
 * @param heapArray - The heap array.
 * @param indexToIncrease - The index where the key needs to be increased.
 * @param newKeyValue - The new key value which should be larger than the
 *   current key value at index i.
 * @throws If the new key is smaller than the current key at index i.
 */
function heapIncreaseKey(
  heapArray: Heap,
  indexToIncrease: number,
  newKeyValue: number,
): void {
  if (newKeyValue < heapArray.heap[indexToIncrease]) {
    throw new Error('new key is smaller than current key');
  }

heapArray.heap[indexToIncrease] = newKeyValue;
  while (
    indexToIncrease > 0 &&
    heapArray.heap[computeParentIndex(indexToIncrease) ?? 0] <
      heapArray.heap[indexToIncrease]
  ) {
    exchangeHeapElements(
      heapArray,
      indexToIncrease,
      computeParentIndex(indexToIncrease) ?? 0,
    );
    indexToIncrease = computeParentIndex(indexToIncrease) ?? 0;
  }
}

/**
 * Inserts a new key into the heap.
 *
 * @param heapArray - The heap array.
 * @param keyToInsert - The key to be inserted into the heap.
 */
function maxHeapInsert(heapArray: Heap, keyToInsert: number): void {
  if (!heapArray.heapSize) throw new Error('Missing heapSize');
  heapArray.heapSize++;
  heapArray.heap[heapArray.heapSize] = -Infinity;
  heapIncreaseKey(heapArray, heapArray.heapSize, keyToInsert);
}

/**
 * Maintains the max-heap property by letting a value at a given index "float
 * down" in the heap.
 *
 * @param heapArray - The heap array.
 * @param index - Index of the element that might violate the max-heap property.
 */
function maxHeapify(heapArray: Heap, index: number): void {
  const leftChildIndex = computeLeftChildIndex(heapArray, index) ?? 0;
  const rightChildIndex = computeRightChildIndex(heapArray, index) ?? 0;
  let largest =
    leftChildIndex &&
    leftChildIndex <= heapArray.heapSize &&
    heapArray.heap[leftChildIndex] > heapArray.heap[index]
      ? leftChildIndex
      : index;

if (
    rightChildIndex &&
    rightChildIndex <= heapArray.heapSize &&
    heapArray.heap[rightChildIndex] > heapArray.heap[largest]
  ) {
    largest = rightChildIndex;
  }

if (largest !== index) {
    exchangeHeapElements(heapArray, index, largest);
    maxHeapify(heapArray, largest);
  }
}

/**
 * Builds a max-heap from an unsorted array.
 *
 * @param heapArray - The heap array to be transformed into a max-heap.
 */
function buildMaxHeap(heapArray: Heap): void {
  heapArray.heapSize = heapArray.length - 1;
  for (let i = Math.floor(heapArray.heapSize / 2); i >= 0; i--) {
    maxHeapify(heapArray, i);
  }
}

/**
 * Performs heapsort on an array, sorting it in place.
 *
 * @param heapArray - The array to be sorted using the heap sort algorithm.
 */
function heapsort(heapArray: Heap): void {
  buildMaxHeap(heapArray);
  for (let i = heapArray.length - 1; i > 0; i--) {
    exchangeHeapElements(heapArray, 0, i);
    if (heapArray.heapSize) heapArray.heapSize--;
    maxHeapify(heapArray, 0);
  }
}

// Usage
(() => {
  const assertEquals = (a: any, b: any) => {
    if (a !== b) {
      throw new Error(`Expected ${b} but got ${a}`);
    }
  };

// Sort
  const heapArray1 = new Heap([4, 1, 3, 2, 16, 9, 10, 14, 8, 7]);
  heapsort(heapArray1);
  assertEquals(heapArray1.toString(), '1,2,3,4,7,8,9,10,14,16');

// Build Max Heap
  const heapArray2 = new Heap([4, 1, 3, 2, 16, 9, 10, 14, 8, 7]);
  buildMaxHeap(heapArray2);
  assertEquals(heapArray2.toString(), '16,14,9,10,8,1,4,2,3,7');
  assertEquals(getHeapMaximum(heapArray2), 16);

// Heap Extract Max
  const heapArray3 = new Heap([4, 1, 3, 2, 16, 9, 10, 14, 8, 7]);
  buildMaxHeap(heapArray3);
  assertEquals(heapExtractMax(heapArray3), 16);
  assertEquals(heapExtractMax(heapArray3), 14);
  assertEquals(heapExtractMax(heapArray3), 10);
  assertEquals(heapExtractMax(heapArray3), 9);
  assertEquals(heapExtractMax(heapArray3), 8);
  assertEquals(heapExtractMax(heapArray3), 7);
  assertEquals(heapExtractMax(heapArray3), 4);

// Heap Increase Key
  const heapArray4 = new Heap([4, 1, 3, 2, 16, 9, 10, 14, 8, 7]);
  buildMaxHeap(heapArray4);
  heapIncreaseKey(heapArray4, 6, 15);
  assertEquals(heapArray4.toString(), '16,15,9,14,8,1,10,2,3,7');

// Max Heap Insert
  const heapArray5 = new Heap([4, 1, 3, 2, 16, 9, 10, 14, 8, 7]);
  buildMaxHeap(heapArray5);
  maxHeapInsert(heapArray5, 15);
  assertEquals(heapArray5.toString(), '16,15,14,10,8,9,4,2,3,7,1');
})();