将关键字序列 (12,2,16,30,8,28,4,10,20,6,18)变成最小堆序列)
时间: 2024-03-19 10:42:59 浏览: 19
将关键字序列依次插入到一个空的堆中,得到的就是一个最小堆序列。
具体过程如下:
1. 将序列的第一个元素 12 插入到堆中,此时堆中只有一个节点,为根节点。
2. 将序列的第二个元素 2 插入到堆中,此时 2 成为根节点的左儿子。
3. 将序列的第三个元素 16 插入到堆中,此时 16 成为根节点的右儿子。但是此时根节点的值大于其右儿子,需要进行交换,交换后根节点的值为 2,左儿子为 16,右儿子为 12。
4. 将序列的第四个元素 30 插入到堆中,此时 30 成为根节点的右儿子。
5. 将序列的第五个元素 8 插入到堆中,此时 8 成为 2 的左儿子。
6. 将序列的第六个元素 28 插入到堆中,此时 28 成为 30 的左儿子。但是此时 2 的左儿子的值大于其右儿子,需要进行交换,交换后 2 的左儿子的值为 8,右儿子的值为 16。
7. 将序列的第七个元素 4 插入到堆中,此时 4 成为 8 的左儿子。
8. 将序列的第八个元素 10 插入到堆中,此时 10 成为 8 的右儿子。
9. 将序列的第九个元素 20 插入到堆中,此时 20 成为 16 的左儿子。但是此时 8 的值大于其左儿子,需要进行交换,交换后 8 的左儿子的值为 4,右儿子的值为 10。
10. 将序列的第十个元素 6 插入到堆中,此时 6 成为 4 的左儿子。
11. 将序列的第十一个元素 18 插入到堆中,此时 18 成为 16 的右儿子。但是此时 4 的值大于其左儿子,需要进行交换,交换后 4 的左儿子的值为 6,右儿子的值为 10。
最终得到的最小堆序列为:2,8,4,10,6,16,18,30,12,20,28。
相关推荐
![](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)