function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
function heapify(arr, n, i) {
let largest = i;
let left = 2 * i + 1;
let right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest !== i) {
swap(arr, i, largest);
heapify(arr, n, largest);
}
}
function heapSort(arr) {
for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
heapify(arr, arr.length, i);
}
for (let i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, i, 0);
}
}