function heapsort(items) { // O(n*log n)
buildHeapInPlace(items);
let heapAreaEnd = items.length - 1;
// while runs n-1 times = O(n)
while (heapAreaEnd > 1) {
swap(items, 0, heapAreaEnd);
--heapAreaEnd;
// O(log n)
iterativeHeapifyDown({ items, currItemPosition: 0, lastHeapIndex: heapAreaEnd });
// now heapifyDown receives the lastHeapIndex, to change only heapArea
}
// return items; // not needed since heapsort is in place
}
const arr = [1, 2, 9, 4, 5, 6];
console.log('before: arr', arr) // [ 1, 2, 9, 4, 5, 6 ]
heapsort(arr)
console.log('after arr', arr) // [ 1, 2, 4, 5, 6, 9 ]
// simplifying: get biggest item (root) and put it at the end of heap area
// now the last item is in the correct position
// --> fix new root that breaks heap property, heapifyDown()
// repeat until all items are in the correct position