堆的认识

概念

堆是一种图的数据结构，被用于实现“优先队列”。优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为“结点(node)”，数据就存储在这些节点中。

堆的特点

如图所示，每个节点由两个子节点，用线条连接即为堆。

• 结点内的数字就是存储的数据
• 堆中的每个结点最多有两个子节点
• 树的形状取决于数据的个数
• 节点的排列顺序为从上到下，同一行里则为从左到右
• 堆的父节点必须小于子结点

堆的数据存储

在堆中存储数据时必须遵守这样一条规则：子结点必定大于父节点

• 顶端的结点为根节点存储的数据为堆中的最小值
• 新数据增加时会被放在堆的最底部靠左的位置
• 堆的底部没有多余空间时，会另起一行把数据加在这一行的最左端

例如，将数字5添加到堆中

• 结点6有个空位置，将数字5加在结点6中

• 数字5结点的父结点大于本身，故调换位置

• 交换完毕后数字5结点的父节点小于本身，所以不再交换，往堆中插入数据5的操作结束

堆的数据获取

从堆中获取数据时，需要从最上面的数据开始取，取完数据后，堆需要进行重新排序，将最后的数据移到取出的结点位置。

如图所示，取出堆中的数字1。

• 1被取出后，结构需要重新调整

• 将最后的数字6结点移到最顶部

• 如果子结点的数字小于父节点，就将父节点与其左右两个子节点中较小的一个进行交换

• 数字6结点的子结点3和5，3为较小者。故与3进行位置调换

• 交换后，数字6结点的两个子节点4和8，4为较小者。故与4进行位置交换

• 交换后，数字6结点无子节点。故交换完毕，从堆中取出数据的操作完成

写在最后

• 文中使用的图片源自《我的第一本算法书》，如若侵权，请评论区留言，作者立即删除相关图片。