与树相同，堆 ( Heap ) 也是一种树形的数据结构，本文所有堆都使用二叉堆实现

二叉堆

在 二叉树 这篇文章中我们学过满二叉树以及完全二叉树，而二叉堆就是一棵完全二叉树

如果你忘记了什么是完全二叉树可以回去看看

如下图就是一棵二叉堆 ( 有点丑 )

我们可以称堆的根结点 ( 1 ) 为堆顶

但是，如果堆仅仅是一个完全二叉树就不至于把它单独拿出来讲了，堆还有一个重要的特点，堆的每个结点存储的是以其为堆顶的新的二叉堆的最优值，并通过一层层的传递，根结点存储的就是整棵树的最优值了

为什么要使用二叉堆

首先我们来看看优先队列，在 队列 中我们曾手打过低配版的优先队列 ( 即在数组的基础上，与其前一个数进行比较，在不满足条件时交换，从而时队头为最优解 )，分析复杂度可知，如果输入的数据为下降序列，第  次添加数据就需要交换  次，如果要添加  次数据，总的时间复杂度就为 ，效率甚至不如读入后进行一次快速排序，可谓是非常糟糕

为此，我们可以使用二叉堆来解决，并且大大提高效率

堆的种类

常见的堆有大根堆 ( 最大堆 ) 与小根堆 ( 最小堆 )，大根堆的根结点是整个堆的最大值，小根堆的根结点是整个堆的最小值

但是我们将数据放入或拿出堆中时，可能会破坏这样的平衡，导致最小值 / 最大值不是根结点了，于是就需要使用一些操作来保持堆的形态

堆的操作

堆作为一个数据结构，就是用来存储，管理数据的，它有点像队列，只允许从删除堆顶 ( 出堆 ) 和从末尾添加结点 ( 入堆 )

但是，有时添加 / 删除了结点后，就将堆的性质破坏了，这时我们就需要用上浮和下沉来维护堆的结构

入堆操作

我们将下面  个数据依次放入一个小根堆中

并使用  来记录堆第  处的数据，使用  来记录堆的最后一个地方

根据二叉树的性质可知

• 一个结点 ( 非根结点 ) 的父亲结点为 : 

• 一个结点 ( 非叶子结点 ) 的左儿子结点为 : 

• 一个结点 ( 非叶子结点 ) 的右儿子结点为 : 
  

先在  的位置放入第一个数 13，这时将  增加 1，代码实现如下

再放入 5，这时，先将它放在最后一个地方 ( 即结点  的地方 )

这个时候，发现这棵树并不满足小根堆的性质，需要我们进行调整，要把结点 2 往上抬，这个操作称为上浮，对父结点进行检测，如果父亲结点的值大于自己，就将自己与父亲结点的值交换，代码实现如下

于是，这棵树又重新满足了小根堆的性质，重新变回了堆

下一个添加的是 -3，并将其放在结点 3 的位置

这棵树再一次不满足小根堆的性质，于是我们要再次对其进行上浮操作，这个时候我们对比低配版的优先队列发现，同样的操作，二叉堆版优先队列仅需交换 1 次，而低配版优先队列需要交换 2 次，效率直接翻倍

并且，随着二叉堆的层数不断增加，并且在最差的情况下 ( 新加入的数为最小值 )，交换的次数仅仅为  次，而低配版需要交换整整  次

事实上，二叉堆每次上浮都排除了相当多的结点，这也是其更加快的原因

正确性证明

我们知道，二叉堆的堆顶存放的一定是这个堆最优的解，如果需要进行上浮的数据要比这个堆的堆顶数据更优，那它就一定比这个堆的其他结点的数据更优，所以上浮是正确的

下一个放入的数据是 9，还是先放入进来

放入后，树再次不满足小根堆的性质，再次进行上浮操作，但不同的是，这一次不是上浮至堆顶，而是在合适的位置停下

将全部数据放入后就就会得到下面的二叉堆 ( 可以自己先模拟建堆，然后再来看看是否正确 )

最终入堆代码如下

时间复杂度 ( 最差 ) : 

出堆操作

学会了添加操作，接下来学习删除操作

前面提到在删除时只能删除堆顶，但是删除完堆顶后，裂开来的两个堆要怎么合并起来呢

还是使用上面建好的堆，依次删除堆的堆顶

删除堆顶后，堆就裂成了两半，变成了这样

这就像一个团队没有了领头一样，所以，我们要找一个临时的领头来代替删除的结点，因为其他节点 ( 除最后一个结点以外的结点 ) 都不好移动，所以就选择了最后一个结点作为新的领头

虽然现在两个堆重新合并了，但是问题仍然明显，结点 1 并不是这个堆的最优解 ( 而是最差解 )，这时就要用到把结点 1 往下降，这个操作称作下沉操作

不同的是，上浮操作不用选，直接与父亲结点交换，可是下沉操作可以下沉到左儿子和右儿子，这时应该选择下沉到哪里呢

思考上方的二叉堆，如果我们选择将结点 1 下沉至其左儿子处，那么就会得到这样二叉堆

显然 -1 的位置是错误的，因为它并不比 3 号结点更优

但如果将结点 1 下沉至其右儿子处，那么就会的到这样的二叉堆

所以我们要将堆顶与较小的儿子结点进行交换操作

正确性证明

在每一次下沉操作中，可以确定的是其左右子结点是其堆中的最优解，也就是说，左右子结点为第 1 及第 2 优的答案

显然的，我们需要将最优的答案放在堆顶，即选择第 1 优的答案并与其进行交换，每一次选择也并不会重新影响之前的选择，所以进行一次完整的下沉操作是正确的

将结点 3 继续下沉，就可以得到

下面为实现下沉的代码，需要注意的都在其中写了

继续删除结点 1，并使用结点 7 进行替代，不断进行，最后弹出的顺序为 ( 可以自己先模拟一下，对比看一下是否正确 )

可见，序列按照从小到大排好了顺序

最终出堆代码如下

时间复杂度 ( 最差 ) : 

完整代码

STL 堆 ( 优先队列 )

详见 队列 中 定义及使用优先队列 部分，本文不再赘述

好了那么关于数据结构二叉堆的内容就讲到这里了

如果你觉得本篇文章对你有所帮助的话，请不要忘记三连支持哦！