34 行
736 字符
1
export function heapSort(values) {
2
const arr = [...values];
3
const n = arr.length;
4
5
// Build max heap
6
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
7
heapify(arr, n, i);
8
}
9
10
// Extract elements one by one
11
for (let i = n - 1; i > 0; i--) {
12
[arr[0], arr[i]] = [arr[i], arr[0]];
13
heapify(arr, i, 0);
14
}
15
16
return arr;
17
}
18
19
function heapify(arr, size, root) {
20
let largest = root;
21
const left = 2 * root + 1;
22
const right = 2 * root + 2;
23
24
if (left < size && arr[left] > arr[largest]) {
25
largest = left;
26
}
27
if (right < size && arr[right] > arr[largest]) {
28
largest = right;
29
}
30
if (largest !== root) {
31
[arr[root], arr[largest]] = [arr[largest], arr[root]];
32
heapify(arr, size, largest);
33
}
34
}