Heap Sort Algorithm
Heap Sort constructs a Max Heap from input array elements and repeatedly extracts the maximum root element, placing it at the end of the array to achieve O(N log N) in-place sorting.
Heap Sort Execution Trace
Build Max-Heap
Transform input array into a valid Max-Heap where parent >= children.
Unsorted: [4, 10, 3, 5, 1] -> Max-Heapified: [10, 5, 3, 4, 1]Extract Max Root (10)
Swap root 10 with last element 1. Reduce heap size and heapify root.
Swap(10, 1) -> [1, 5, 3, 4, 10] -> Heapify(0) -> [5, 4, 3, 1, 10]Extract Next Root (5)
Swap root 5 with last un-sorted element 1. Heapify root to restore heap property.
Swap(5, 1) -> [1, 4, 3, 5, 10] -> Heapify(0) -> [4, 1, 3, 5, 10]Real-world analogy: Winner Podium Extraction
Build a tournament pyramid structure. Pull the champion off the top podium, put them in 1st place, and run a fast playoff to find the next champion.
- Max Heapify= Restores heap condition in O(log N) time.
Complexity analysis
~4,483 steps (Linearithmic)
O(N log N) Linearithmic Time
O(log N) Stack
Memory growth rate as N expands.
Relative efficiency rating for large N.
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Best / Average / Worst Case | O(N log N) | O(1) |
Code implementations
function heapSort(arr) {
// Build Max-Heap and extract elements
return arr;
}Real-world applications
Embedded Systems
Guarantees O(N log N) worst-case time with strictly zero dynamic memory allocation.
Interview questions
Topic Knowledge Test & Assessment
Heap Sort Knowledge & Skill Test
Validate your conceptual understanding, operation mechanics, and core concepts of Heap Sort.
Topic Metadata
Unlike Quick Sort, Heap Sort guarantees strict O(N log N) worst-case time without requiring extra auxiliary memory!