Heap Sort
Visualize Heap Sort, a selection-based sort using a Binary Heap to efficiently find the max element.
Root/Node
Compare
Swap
Sorted
4
10
3
5
1
Ready to sort
1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Imagine a corporate hierarchy where the boss (largest number) must always be at the top. We repeatedly remove the boss, send them to retirement (sorted end), and promote a new boss, adjusting the hierarchy until everyone is retired (sorted).
Concept
- Max Heap: A binary tree where Parent >= Children. Root is always the Max.
- Heapify: The process of restoring the heap property after the root changes.
- In-Place: Uses the same array to store the heap and the sorted result.
How it Works
Algorithm:
- Build a Max Heap from the input array.
- Swap the Root (Max) with the last element.
- Reduce heap size by 1 (the last element is now sorted).
- Heapify the new Root to restore Max Heap property.
Step-by-Step Breakdown
Watch the visualization:
- Blue Highlight: Current Node being heapified (e.g., Parent).
- Orange Bar: Comparison with children.
- Red Bar: Swapping to fix heap property or move Max to end.
- Green: Sorted element at the end of the array.
When to Use
- Guaranteed O(N log N): Good worst-case performance unlike Quick Sort.
- Space Constraints: O(1) extra space.
- Priority Queues: Excellent for finding the 'Top K' items.
When NOT to Use
- Cache Performance: Poor locality of reference compared to Quick Sort.
- Stable Sort Required: It is unstable.
How to Identify
"Top K Elements", "Priority Queue", "Heaps".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.