25 行
650 字符
1
function heapSort(arr) {
2
const n = arr.length;
3
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
4
heapify(arr, n, i);
5
}
6
for (let i = n - 1; i > 0; i--) {
7
[arr[0], arr[i]] = [arr[i], arr[0]];
8
heapify(arr, i, 0);
9
}
10
return arr;
11
}
12
13
function heapify(arr, size, root) {
14
let largest = root;
15
const left = 2 * root + 1;
16
const right = 2 * root + 2;
17
if (left < size && arr[left] > arr[largest]) largest = left;
18
if (right < size && arr[right] > arr[largest]) largest = right;
19
if (largest !== root) {
20
[arr[root], arr[largest]] = [arr[largest], arr[root]];
21
heapify(arr, size, largest);
22
}
23
}
24
25
module.exports = heapSort;