Implementation of heapsort in JavaScript.

heapsort.js

// Implementation of heapsort in JavaScript.

LENGTH = 1e2;
MAX = 2e4;
MIN = 1;

function generateInput(min, max, length) {
  const res = [];
  while (res.length < length) {
    res.push(Math.round(Math.random() * (max - min) + min));
  }
  return res;
}

function getParent(i) {
  return i >> 1;
}

function getLeft(i) {
  return i << 1;
}

function getRight(i) {
  return (i << 1) + 1;
}

function maxHeapify(heap, i) {
  const l = getLeft(i);
  const r = getRight(i);
  let largest = i;
  if (l && l <= heap.heapSize && heap[l] > heap[i]) {
    largest = l;
  }
  if (r && r <= heap.heapSize && heap[r] > heap[largest]) {
    largest = r;
  }
  if (largest !== i) {
    const oldI = heap[i];
    heap[i] = heap[largest];
    heap[largest] = oldI;
    maxHeapify(heap, largest);
  }
}

function buildMaxHeap(input) {
  input.heapSize = input.length - 1;
  for (let i = Math.floor((input.length - 1) / 2); i > 0; i--) {
    maxHeapify(input, i);
  }
}

function heapSort(input) {
  // fill the 0 index so we can start from 1 (we need this because math).
  input.unshift(null);
  buildMaxHeap(input);
  for (i = input.length - 1; i > 1; i--) {
    const first = input[1];
    input[1] = input[i];
    input[i] = first;
    input.heapSize = input.heapSize - 1;
    maxHeapify(input, 1);
  }
  // Remove that first item.
  input.shift();
}

const input = generateInput(MIN, MAX, LENGTH);
heapSort(input);
console.log(input);