概念
堆是一种图的数据结构，被用于实现“优先队列”。
优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为“结点(node)”，数据就存储在这些节点中。
堆的特点
如图所示，每个节点由两个子节点，用线条连接即为堆。
- 结点内的数字就是存储的数据
- 堆中的每个结点最多有两个子节点
- 树的形状取决于数据的个数
- 节点的排列顺序为从上到下，同一行里则为从左到右
- 堆的父节点必须小于子结点
堆的数据存储
在堆中存储数据时必须遵守这样一条规则：子结点必定大于父节点
- 顶端的结点为根节点存储的数据为堆中的最小值
- 新数据增加时会被放在堆的最底部靠左的位置
- 堆的底部没有多余空间时，会另起一行把数据加在这一行的最左端
例如，将数字5添加到堆中
- 结点6有个空位置，将数字5加在结点6中
- 数字5结点的父结点大于本身，故调换位置
- 交换完毕后数字5结点的父节点小于本身，所以不再交换，往堆中插入数据5的操作结束
堆的数据获取
从堆中获取数据时，需要从最上面的数据开始取，取完数据后，堆需要进行重新排序，将最后的数据移到取出的结点位置。
如图所示，取出堆中的数字1。
- 1被取出后，结构需要重新调整
- 将最后的数字6结点移到最顶部
- 如果子结点的数字小于父节点，就将父节点与其左右两个子节点中较小的一个进行交换
- 数字6结点的子结点3和5，3为较小者。故与3进行位置调换
- 交换后，数字6结点的两个子节点4和8，4为较小者。故与4进行位置交换
- 交换后，数字6结点无子节点。故交换完毕，从堆中取出数据的操作完成
写在最后
- 文中使用的图片源自《我的第一本算法书》，如若侵权，请评论区留言，作者立即删除相关图片。
- 文中如有错误，欢迎在评论区指正，如果这篇文章帮到了你，欢迎点赞和关注😊
- 本文首发于掘金，未经许可禁止转载💌
评论区