Heap sort

Medium

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: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}