阅读 209

数据结构:堆

概念

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

堆的特点

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

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

堆的数据存储

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

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

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

  • 结点6有个空位置,将数字5加在结点6中
  • 数字5结点的父结点大于本身,故调换位置
  • 交换完毕后数字5结点的父节点小于本身,所以不再交换,往堆中插入数据5的操作结束

堆的数据获取

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

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

  • 1被取出后,结构需要重新调整
  • 将最后的数字6结点移到最顶部
  • 如果子结点的数字小于父节点,就将父节点与其左右两个子节点中较小的一个进行交换
  • 数字6结点的子结点3和5,3为较小者。故与3进行位置调换
  • 交换后,数字6结点的两个子节点4和8,4为较小者。故与4进行位置交换
  • 交换后,数字6结点无子节点。故交换完毕,从堆中取出数据的操作完成

写在最后

  • 文中使用的图片源自《我的第一本算法书》,如若侵权,请评论区留言,作者立即删除相关图片。
  • 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊
  • 本文首发于掘金,未经许可禁止转载💌
关注下面的标签,发现更多相似文章
评论