Heap Sort [JavaScript]

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements efficiently. It begins by building a max heap (or min heap, depending on sorting order) from the input list. In a max heap, the largest element is always at the root. The algorithm then repeatedly swaps the root element with the last element of the heap, reducing the heap size by one with each iteration. After each swap, it performs a "heapify" operation to restore the max heap property within the reduced heap. This process continues until the entire list is sorted.

Heap sort has a time complexity of \(O(n \log n)\), as building the heap takes \(O(n)\) time, and each of the \(n\) removal operations requires \(O(\log n)\) time for heapify. Heap sort is efficient and suitable for large datasets, as it requires no additional memory beyond the input list (in-place sorting). However, it is not stable, meaning it does not preserve the relative order of equal elements.

https://adamdjellouli.com/tools/sorting/

Видео Heap Sort [JavaScript] канала Adam Djellouli