function getLeftChildIndex(parentIndex: number): number {
return 2 * parentIndex + 1;
}
function getRightChildIndex(parentIndex: number): number {
return 2 * parentIndex + 2;
}
function heapify(arr: number[], parentIndex: number, n: number): void {
let childIndex: number = getLeftChildIndex(parentIndex);
while (childIndex < n) {
if (getRightChildIndex(parentIndex) < n &&
arr[getLeftChildIndex(parentIndex)] < arr[getRightChildIndex(parentIndex)]) {
childIndex = getRightChildIndex(parentIndex);
}
if (arr[parentIndex] >= arr[childIndex]) break;
[arr[childIndex], arr[parentIndex]] = [arr[parentIndex], arr[childIndex]]
parentIndex = childIndex;
childIndex = getLeftChildIndex(childIndex);
}
}
function heapSort(arr: number[]): void {
for (let i: number = (arr.length - 1) / 2; i >= 0; --i) {
heapify(arr, i, arr.length)
}
for (let i: number = arr.length - 1; i > 0; --i) {
[arr[i], arr[0]] = [arr[0], arr[i]]
heapify(arr, 0, i);
}
}
const arr = [4, 5, 1, 3, 2];
console.log('排序前: ', arr);
heapSort(arr);
console.log('排序后: ', arr);