Given a max heap H = [40,30,15,10,20], draw the intermediate heaps while conducting the heap sort algorithm.
时间: 2023-05-28 19:07:49 浏览: 72
Intermediate heaps during heap sort algorithm:
Step 1: Remove the root node (40) and replace it with the last node (20). The heap becomes [20,30,15,10,40].
```
40
/ \
30 15
/ \
10 20
20
/ \
30 15
/
10
\
40
```
Step 2: Heapify the heap to maintain the max heap property. The heap becomes [30,20,15,10,40].
```
20
/ \
30 15
/
10
\
40
30
/ \
20 15
/
10
\
40
```
Step 3: Remove the root node (30) and replace it with the last node (10). The heap becomes [10,20,15,30,40].
```
30
/ \
20 15
/
10
\
40
10
/ \
20 15
/
30
\
40
```
Step 4: Heapify the heap to maintain the max heap property. The heap becomes [20,10,15,30,40].
```
10
/ \
20 15
/
30
\
40
20
/ \
10 15
/
30
\
40
```
Step 5: Remove the root node (20) and replace it with the last node (15). The heap becomes [15,10,20,30,40].
```
20
/ \
10 15
/
30
\
40
15
/ \
10 20
/
30
\
40
```
Step 6: Heapify the heap to maintain the max heap property. The heap becomes [10,15,20,30,40].
```
15
/ \
10 20
/
30
\
40
10
/ \
15 20
/
30
\
40
```
Step 7: Remove the root node (10) and replace it with the last node (40). The heap becomes [40,15,20,30].
```
10
/ \
15 20
/
30
\
40
40
/ \
15 20
/
30
```
Step 8: Heapify the heap to maintain the max heap property. The heap becomes [20,15,40,30].
```
15
/ \
40 20
/
30
20
/ \
15 40
/
30
```
Step 9: Remove the root node (20) and replace it with the last node (30). The heap becomes [40,15,30].
```
20
/ \
15 40
/
30
30
/ \
15 40
```
Step 10: Heapify the heap to maintain the max heap property. The heap becomes [40,15,30].
```
30
/ \
15 40
40
/ \
15 30
```
Step 11: Remove the root node (40) and replace it with the last node (30). The heap becomes [30,15].
```
40
/ \
15 30
30
/
15
```
Step 12: Heapify the heap to maintain the max heap property. The heap becomes [30,15].
```
15
/
30
```
Step 13: Remove the root node (30) and replace it with the last node (15). The heap becomes [15].
```
30
/
15
15
```
Step 14: Heapify the heap to maintain the max heap property. The heap becomes [15].
```
15
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)