Definition
Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort. The improvement consists of the use of a heap data structure instead of a linear-time search to find the maximum or minimum element.
Implementation
- Use recursion.
- Use the spread operator (
...
) to clone the original array,arr
. - Use closures to declare a variable,
l
, and a functionheapify
. - Use a
for
loop andMath.floor()
in combination withheapify
to create a max heap from the array. - Use a
for
loop to repeatedly narrow down the considered range, usingheapify
and swapping values as necessary in order to sort the cloned array.
js
const heapsort = arr => {
const a = [...arr];
let l = a.length;
const heapify = (a, i) => {
const left = 2 * i + 1;
const right = 2 * i + 2;
let max = i;
if (left < l && a[left] > a[max]) max = left;
if (right < l && a[right] > a[max]) max = right;
if (max !== i) {
[a[max], a[i]] = [a[i], a[max]];
heapify(a, max);
}
};
for (let i = Math.floor(l / 2); i >= 0; i -= 1) heapify(a, i);
for (i = a.length - 1; i > 0; i--) {
[a[0], a[i]] = [a[i], a[0]];
l--;
heapify(a, 0);
}
return a;
};
heapsort([6, 3, 4, 1]); // [1, 3, 4, 6]
Complexity
The algorithm has an average time complexity of O(n log n)
, where n
is the size of the input array.