HeapSort (using MaxHeap)

let heapSize;
let arr = [15, 3, 17, 18, 20, 2, 1, 666];

heapSort();
console.log(arr);

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

function maxHeapify(i) {
  let largest;
  let l = 2 * i + 1;
  let r = 2 * i + 2;
  if (l <= heapSize && arr[l] > arr[i]) {
    largest = l;
  } else {
    largest = i;
  }
  if (r <= heapSize && arr[r] > arr[largest]) {
    largest = r;
  }
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    maxHeapify(largest);
  }
}

function heapSort() {
  buildToMaxHeap();
  for (let i = arr.length - 1; i >= 0; i--) {
    [arr[i], arr[0]] = [arr[0], arr[i]];
    heapSize -= 1;
    maxHeapify(0);
  }
  return arr;
}