This algorithm is similar to Selection Sort. It splits the array into a sorted and unsorted region.
It will iterate through the unsorted region and move the max element to the sorted region.
However, it uses the 'max-heap' data structure to do this.
function maxHeapify(arr, i, n) {
let l = 2 * i + 1;
let r = 2 * i + 2;
let largest;
if (l < n && arr[l] > arr[i]) {
largest = l;
} else {
largest = i;
}
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
maxHeapify(arr, largest, n);
}
}
function buildMaxHeap(arr) {
for (let i = Math.floor(arr.length / 2); i >= 0; i--) {
maxHeapify(arr, i, arr.length);
}
}
function maxHeapSort(arr) {
buildMaxHeap(arr);
let s = arr.length;
for (let i = arr.length - 1; i >= 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
s--;
maxHeapify(arr, 0, s);
}
return arr;
}