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

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

原文出自 ：原文

1.简介

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

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

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

3.最小堆的构建

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

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

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

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

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

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

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

以下是本示例的图解：
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

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

在这里插入图片描述

在这里插入图片描述

4.最小堆的元素插入

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

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

以下是插入操作的图解：

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

5.最小堆的节点删除

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

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

以下是图解：

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

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

发表评论

表情：
评论列表 （有 0 条评论，113人围观）

还没有评论，来说两句吧...

相关阅读

    相关 堆（建立，插入，删除）

    首先定义优先队列，优先队列是一种特殊的队列，取出元素的顺序是依据优先权（关键字）的大小，而不是元素进出队列的顺序。 如果使用二叉搜索树存储这个优先队列，就构成了“堆”结构。

    短命女短命女/ 0 赞/ 32 阅读

    相关 【数据结构】最大堆的插入与删除

    堆是一种特殊的队列，从堆中取出元素的顺序不是按照元素进入队列的先后顺序，而是依据元素的优先权，或者说是大小，所以堆也叫做“优先队列”。 堆最常使用二叉树结构表示，可以看作是

    红太狼红太狼/ 0 赞/ 262 阅读