Heap sort
Problem
Sort an array in place by building a max-heap and then repeatedly swapping the maximum to the end and sifting down. O(n log n) time, O(1) space, not stable.
Example 1
Input: [12, 11, 13, 5, 6, 7] Output: [5, 6, 7, 11, 12, 13]
Also asked as: Sort an Array using heap. (HeapSort)
Test cases
Case 1
Input: [12,11,13,5,6,7] Expected: [5,6,7,11,12,13]
Case 2
Input: [3,1,2,3,1] Expected: [1,1,2,3,3]
Case 3
Input: [1] Expected: [1]
Case 4
Input: [] Expected: []
View solutionHide solution1 approach
1. Build max-heap in place, repeatedly extract the max to the end
Time O(n log n)Space O(1)
Heapify the array into a max-heap; swap the root with the last unsorted element and sift down the reduced heap. In place, O(1) extra.
function heapSort(a) { const n = a.length; const down = (i, size) => { for (;;) { let s = i, l = 2 * i + 1, r = 2 * i + 2; if (l < size && a[l] > a[s]) s = l; if (r < size && a[r] > a[s]) s = r; if (s === i) break; [a[s], a[i]] = [a[i], a[s]]; i = s; } }; for (let i = (n >> 1) - 1; i >= 0; i--) down(i, n); for (let end = n - 1; end > 0; end--) { [a[0], a[end]] = [a[end], a[0]]; down(0, end); } return a;}