Heap Sort
Sortingmedium#6Build max-heap, repeatedly extract maximum to sort
Ready
Step 1 of 0
Speed
Input Data
Comma-separated numbers (0-999). Min 2 values.
Algorithm Code
1function heapSort(arr) {2 const n = arr.length;3 for (let i = Math.floor(n/2) - 1; i >= 0; i--)4 heapify(arr, n, i);5 for (let i = n - 1; i > 0; i--) {6 [arr[0], arr[i]] = [arr[i], arr[0]];7 heapify(arr, i, 0);8 }9}10function heapify(arr, n, i) {11 let largest = i;12 const l = 2*i + 1, r = 2*i + 2;13 if (l < n && arr[l] > arr[largest]) largest = l;14 if (r < n && arr[r] > arr[largest]) largest = r;15 if (largest !== i) {16 [arr[i], arr[largest]] = [arr[largest], arr[i]];17 heapify(arr, n, largest);18 }19}
Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(1)
About Heap Sort
Heap Sort builds a max-heap from the array, then repeatedly extracts the maximum element and places it at the end. It combines the advantages of both merge sort (guaranteed O(n log n)) and insertion sort (in-place). Uses a binary heap data structure.
Time Complexity: Best: O(n log n), Average: O(n log n), Worst: O(n log n). Space: O(1).