二叉堆

学习数据结构与算法
2021-05-17 14:29 · 阅读时长7分钟
小课

二叉堆是一种基于二叉树的特殊存储结构,它可以看成是一棵完全二叉树。常见的有最大堆又叫大顶堆、大根堆和最小堆又叫小顶堆、小根堆。在最大堆中的任何一个子树中都有父节点的值都大于子节点的值。在最小堆中的任何一个子树中父节点的值都小于子节点。

更多介绍参考维基百科

注释

虽然二叉堆是基于二叉树的,但是实际中,我们经常使用数组来存储二叉堆,实现逻辑上的树形结构,其具备以下特点:

  • 数组中每一个元素代表二叉堆中的一个节点。
  • 父节点和子节点在数组中的存储位置存在特殊的关系,第i个节点,其左右子节点的存储位置分别是2i+1和2i+2,其父节点的存储位置是floor((i-1)/2)。

比如说使用数组存储的最大堆[100, 19, 36, 17, 3, 25, 1, 2, 7],它树形结构如下。

加载中...

通过上面可以看出,节点17的在数组中的存储位置是3,它的左右子节点存储位置分别是2*3+1=7和2*3+2=8,它的父节点的存储位置是floor((3-1)/2)=1。这个特性在后续操作、维护堆的时候非常有用。

堆的应用
  • 堆排序,利用堆数据结构实现的一种排序算法。
  • 优先队列,很多优先队列的实现都是基于堆。
  • 在图算法中的应用,比如最小生成树Prim算法,还有最短路径Dijkstra算法。

二叉堆最主要的两种操作,插入和删除,因为操作完成之后仍然要维持堆的特性,所以需要对堆中的部分节点进行调整,这两种操作的时间复杂度都是O(logN),下面以最大堆为例,看看堆的插入和删除操作。

插入逻辑

  1. 插入时先将数据插入在二叉堆最后面,也就是数组的尾部。
  2. 然后将当前节点跟它的父节点进行比较。
    *) 如果当前节点大于父节点,则将父节点与当前节点交换。
    *) 如果小于等于父节点,则停止操作。
  3. 重复第2步操作,直到当前节点小于等于父节点。

删除逻辑

  1. 首先用二叉堆最后面的节点替换最顶部的节点,即数组的最后一个元素替换第一个元素。
  2. 然后将当前节点和它的左右子节点一起对比。
    *) 如果左子节点最大,则将当前节点与左子节点交换。
    *) 如果右子节点最大,则将当前节点与右子节点交换。
    *) 如果当前节点最大,则停止操作。
  3. 重复第2步操作,直到当前节点大于等于其左右子节点。

下面看看数组[1,3,2,5,6,4]依次插入到最大堆和从最大堆删除的动画演示。

加载中...

该动画仅演示从顶部删除节点,从中间节点删除逻辑类似。

注释
加载中...
二叉堆优先队列