Loading content…
Sorting Algorithms
Heap Sort builds a max-heap, repeatedly moves the largest value to the end, and restores the heap for the remaining items.
Heap Sort first arranges the array into a binary heap where the maximum value sits at the root.
It then swaps that root with the last unsorted element, shrinks the heap, and heapifies again.
It guarantees O(n log n) time and is a good way to understand the connection between arrays and tree-shaped data.
This implementation builds a max-heap in place and repeatedly restores heap order after moving the maximum to the end.
// Логически делим массив на тройки (корень - левый лист и правый лист)
// Выясняем кто из тройки наибольший и помещаем его в корень
// O(nlog(n))
function heapSort (arr) {
const n = arr.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, i, n);
}
for (let i = n - 1; i > 0; i--) {
const temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
heapify(arr, 0, i);
}
return arr;
}