```
🏔️ HEAP SORT VISUALIZER
Build Max Heap • Compare • Swap • Extract Maximum • Sort
```
```
📥 Enter Your Data
```
```
📊 Array Visualization
Enter values and press START HEAP SORT.
```
```
🌳 Max Heap Visualization
```
```
```
📈 Live Statistics
Phase
0
Comparisons
0
Swaps
0
Heap Size
0
Steps
0
```
```
📝 Step-by-Step Explanation
1
Heap Sort first creates a
Max Heap.
The largest element is placed at the root.
```
🧮 Heap Sort Mathematics
For a node at index i:
Left Child: 2i + 1
Right Child: 2i + 2
Parent: ⌊(i - 1) / 2⌋
For Max Heap:
Parent ≥ Left Child
Parent ≥ Right Child
Root contains the:
Maximum Element
```
Left Child: 2i + 1
Right Child: 2i + 2
Parent: ⌊(i - 1) / 2⌋
For Max Heap:
Parent ≥ Left Child
Parent ≥ Right Child
Root contains the:
Maximum Element
```
🔢 Complete Mathematical Example
Initial Array:
4, 10, 3, 5, 1
Start from the last non-leaf node.
Last non-leaf index:
⌊n/2⌋ − 1
For n = 5:
⌊5/2⌋ − 1 = 1
Check index 1:
Parent = 10
Children = 5 and 1
10 is already larger.
Check index 0:
Parent = 4
Children = 10 and 3
Largest = 10
Swap:
10, 4, 3, 5, 1
Now the largest value 10 is at the root.
Extract 10:
Swap root with last element.
1, 4, 3, 5 | 10
Heapify:
5 is larger than 1.
Swap:
5, 4, 3, 1 | 10
Repeat until all elements are extracted.
Final:
1, 3, 4, 5, 10
```
4, 10, 3, 5, 1
Start from the last non-leaf node.
Last non-leaf index:
⌊n/2⌋ − 1
For n = 5:
⌊5/2⌋ − 1 = 1
Check index 1:
Parent = 10
Children = 5 and 1
10 is already larger.
Check index 0:
Parent = 4
Children = 10 and 3
Largest = 10
Swap:
10, 4, 3, 5, 1
Now the largest value 10 is at the root.
Extract 10:
Swap root with last element.
1, 4, 3, 5 | 10
Heapify:
5 is larger than 1.
Swap:
5, 4, 3, 1 | 10
Repeat until all elements are extracted.
Final:
1, 3, 4, 5, 10
```
```
⚙️ How Heap Sort Works
1
Build Max Heap:
Arrange the array so that every parent is greater
than or equal to its children.
2
The largest element is now at the root,
index 0.
3
Swap the root with the last element
of the unsorted heap.
4
Reduce the heap size by one.
The extracted largest element is now sorted.
5
Apply heapify to restore the Max Heap property.
6
Repeat the process until only one element remains.
```
```
⚖️ Advantages & Disadvantages
+
Advantages
• Guaranteed O(n log n) time complexity.
• Does not require an additional array like standard Merge Sort.
• Works efficiently for large datasets.
• Uses O(1) auxiliary space when implemented in-place.
• Guaranteed O(n log n) time complexity.
• Does not require an additional array like standard Merge Sort.
• Works efficiently for large datasets.
• Uses O(1) auxiliary space when implemented in-place.
−
Disadvantages
• Usually not stable.
• Heap operations are more difficult to understand than Bubble Sort or Insertion Sort.
• Often has poorer cache behavior than some other O(n log n) sorting algorithms.
• Usually not stable.
• Heap operations are more difficult to understand than Bubble Sort or Insertion Sort.
• Often has poorer cache behavior than some other O(n log n) sorting algorithms.
```
⏱️ Time & Space Complexity
Build Heap
O(n)
Best Case
O(n log n)
Average Case
O(n log n)
Worst Case
O(n log n)
Auxiliary Space:
O(1)
Heap Sort is an in-place sorting algorithm.
```
O(1)
Heap Sort is an in-place sorting algorithm.
No comments:
Post a Comment