Heap Sort
Heap Sort uses a binary heap data structure to sort elements. It first builds a max heap, then repeatedly extracts the maximum element.
AdvancedTime: O(n log n)Space: O(1)
Take QuizCurrent Step
Press Play to start the visualization
## How Heap Sort Works
Heap Sort uses a binary heap data structure to sort elements. It first builds a max heap from the array, then repeatedly extracts the maximum element.
### Algorithm Steps:
1. Build a max heap from the input array
2. The largest element is now at the root
3. Swap root with the last element
4. Reduce heap size by 1 and heapify the root
5. Repeat until heap size is 1
### Key Characteristics:
- **In-place**: Only requires O(1) extra space
- **Not Stable**: May change relative order of equal elements
- **Guaranteed O(n log n)**: No worst-case degradation
Time & Space Complexity
| Case | Time Complexity |
|---|---|
| Best | O(n log n) |
| Average | O(n log n) |
| Worst | O(n log n) |
| Space | O(1) |
Practice Problems
10 problems81 total points
1
Basic Heap Sort
Beginner5 pts
2
Heapify Array
Beginner5 pts
3
Kth Largest Element
Beginner5 pts
4
Min Heap Operations
Intermediate8 pts
5
Sort Characters by Frequency
Intermediate8 pts
6
Merge K Sorted Lists
Advanced10 pts
7
Top K Frequent Elements
Advanced10 pts
8
Sliding Window Maximum
Advanced10 pts
9
Task Scheduler
Advanced10 pts
10
IPO - Maximize Capital
Advanced10 pts