刷题笔记：最小堆构建、插入、删除的过程图解

悠悠 2024-04-18 22:33 142阅读 0赞

原文出自 ：[原文][Link 1]

1.简介

最小堆是一棵完全二叉树，非叶子结点的值不大于左孩子和右孩子的值。本文以图解的方式，说明

最小堆的构建、插入、删除的过程。搞懂最小堆的相应知识后，最大堆与此类似。

2.最小堆示例  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70]

3.最小堆的构建

初始数组为：9,3,7,6,5,1,10,2

按照完全二叉树，将数字依次填入。

填入后，找到最后一个结点（本示例为数字2的节点），从它的父节点（本示例为数字6的节点）

开始调整。根据性质，小的数字往上移动；至此，第1次调整完成。

注意，被调整的节点，还有子节点的情况，需要递归进行调整。

第二次调整，是数字6的节点数组下标小1的节点（比数字6的下标小1的节点是数字7的节点），

用刚才的规则进行调整。以此类推，直到调整到根节点。

以下是本示例的图解：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 3]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 4]

注意：数字9的节点 将和 数字1的节点 发生对调，对调后，需要递归进行调整，请一定注意。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 6]

4.最小堆的元素插入

以上个最小堆为例，插入数字0。

数字0的节点首先加入到该二叉树最后的一个节点，依据最小堆的定义，自底向上，递归调整。

以下是插入操作的图解：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 8]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 10]

5.最小堆的节点删除

对于最小堆和最大堆而言，删除是针对于根节点而言。

对于删除操作，将二叉树的最后一个节点替换到根节点，然后自顶向下，递归调整。

以下是图解：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 11]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 12]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 13]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 14]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 15]

————————————————  
版权声明：本文为CSDN博主「Running07」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/hrn1216/article/details/51465270

[Link 1]: https://blog.csdn.net/hrn1216/article/details/51465270
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d44ab578388e42dcb5ba0e63b978ec98.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/254127869b434c0697e5a0d965df5047.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ae896451eeac4e3bb1364414032f51c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/4586c9e8d1b1437f82ab2ec0d72ad614.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/9604e9203f3b4515b10a81ad53b4abd2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2705bde9bb4444c68f814a5a39015dde.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/24bf1b23abf44b8e96a0ade90bcad72d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/b91e7c0dc29c4b51a1a8fc4de18e7467.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/80aa70ec17284a1aa657476fffa82d6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 9]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/0e334c38110f480f8f8955aeede43e80.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 10]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ec66ba90b7864c0c86283c9888fe57df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 11]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/b17c184ac0a442d3ab4a08883f7a88d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 12]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/a20cc7cd91674af69ef1b2acc75246ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 13]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/3e53eae1cc424fbbbdc1a341b2a85c0d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 14]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/69f5f18456954763ad8b2c906f85a492.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0aGlyZG9uZWw_size_16_color_FFFFFF_t_70 15]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/66dd0418a1514471b647c35397914bdc.png