Loading...
An efficient comparison-based sorting algorithm that uses a binary heap data structure. It guarantees O(n log n) time complexity and is not stable but sorts in-place.
function heapSort(arr) {
const n = arr.length;
// Build max heap (rearrange array)
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements from heap one by one
for (let i = n - 1; i > 0; i--) {
// Move current root to end
[arr[0], arr[i]] = [arr[i], arr[0]];
// Call heapify on the reduced heap
heapify(arr, i, 0);
}
return arr;
}
function heapify(arr, n, i) {
let largest = i; // Initialize largest as root
let left = 2 * i + 1; // Left child
let right = 2 * i + 2; // Right child
// If left child is larger than root
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// If largest is not root
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Time: O(n log n) - always
// Space: O(1) - in-place (if we ignore recursion stack)function heapifyIterative(arr, n, start) {
let parent = start;
while (true) {
let largest = parent;
let left = 2 * parent + 1;
let right = 2 * parent + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest === parent) {
break; // Heap property satisfied
}
[arr[parent], arr[largest]] = [arr[largest], arr[parent]];
parent = largest;
}
}
// Avoids recursion stack
// True O(1) space complexityfunction minHeapSort(arr) {
const n = arr.length;
// Build min heap
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
minHeapify(arr, n, i);
}
// Extract elements (results in descending order)
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
minHeapify(arr, i, 0);
}
return arr;
}
function minHeapify(arr, n, i) {
let smallest = i;
let left = 2 * i + 1;
let right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest]) {
smallest = left;
}
if (right < n && arr[right] < arr[smallest]) {
smallest = right;
}
if (smallest !== i) {
[arr[i], arr[smallest]] = [arr[smallest], arr[i]];
minHeapify(arr, n, smallest);
}
}Unlike Quick Sort, Heap Sort always guarantees O(n log n) performance regardless of input distribution.
Heap Sort has poor cache locality compared to Quick Sort and Merge Sort, making it slower in practice despite same Big O complexity.