Build a max-heap in an array, then repeatedly exchange its root with the last element of the active heap and restore heap order by heapify down. The inactive suffix grows in ascending order. Bottom-up heap construction costs because the number of nodes at height decreases geometrically, and the extraction phase costs . Iterative sifting uses constant auxiliary storage. Long-distance exchanges can reverse equal-key records, so the usual version does not provide stable sorting.
Articles by others on the same topic
Heapsort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It is an efficient sorting technique with a time complexity of \(O(n \log n)\) in the average and worst cases. Heapsort can be broken down into two main phases: building the heap and repeatedly extracting the maximum element from the heap. ### Key Concepts 1.