大家好。这一讲我们继续数据结构与算法第五章二叉树的学习。
今天我们介绍一种重要的数据结构，也就是堆
以及堆跟优先队列的一些相应的应用关系。
堆是这么一种数据结构，我们以最小堆为例。
最小堆它是这么一个关键码的序列。
在这个序列里面呢我们排在第i位的这个元素呢它一定是小于等于排在第
2i+1位的元素和2i+2的这个元素
我们把它画成这么一个完全二叉树的形式
就可以看出实际上它对应的来说，就是在某一个子根结点
那它呢一定是小于它的左右
孩子的这样的关键码，当然也可以等于。
那类似的，我们可以定义最大堆。堆实际上是完全二叉树的
层次序列。因此我们可以用数组存储。
堆里面它的这样的一些约束是比较
松散的，也就是他最主要的是父子之间的这样的约束。
对于兄弟结点之间它是没有一个强制的限制的。
因此堆不是唯一的，也就是说对于这么一组数
那我建的有各种情况都满足最小堆的定义。当然它们的共同特点就是
最小值一定是出现在根这个方向上。
那从逻辑角度来看，我们都可以看到了
堆它还是一种树形结构，而且是一种完全二叉树的结构。
那堆呢我们可以用数组来实现它。
因此我们会有一个存放数据的数组以及这个数组的最大元素的
个数，还有当前堆里面的有效元素的个数。
那作为一种数据结构我们往往会要定义它相应的增删查改等等
这些运算。那作为它的二叉树的这样的逻辑结构呢 我们显然就会有
左右子结点以及父结点等等这样的相关的运算。在堆里面呢它特别重要的运算
就是我们删除这个最小元素，因为在整个这个堆里面我们
找最小值是最方便的，但是在最大堆里面我们找最大值是很方便的。
那找到以后呢往往它就是进入一个服务序列
也就是说出堆了，那在优先队里面往往就是这样的。
那堆里面还有两个特别重要的运算呢就是SiftUp和SiftDown。
那这个有一点类似于栈里面的入栈出栈和队列里面的
入队列出队列。那它是非常基础的运算，我们先来看一下在最小堆里面
用筛法来SiftDown的一个调整的过程。
因为它是最小堆，那我们
假设对于这么一个子树整个这个72为根的是一个子树。
那它的左子树和右子树
都是已经成为最小堆。那现在我们在这个根的位置进行一个调整。
那我们就只需要进行SiftDown的操作就是在它的左右子结点里面找到
那个最小然后呢它跟最小的这个进行交换。
然后继续一直到这个原来所在的这个子根的这个数值
它带到一个合适的位置。这个位置不一定是在最后的这个叶结点
也可能呆在那儿不用动，也可能是呆在某一个位置。
那我们这个算法就是起先这么一个SiftDown的过程。
那因为我们刚才强调它只是一个子树，它并不一定是从根那个
0下标位开始所以我们有一个起始的一个position的这个位置。那在这个位置
开始我们先把这个当前的这个下标i就赋为
position，然后它的左子孩子的下标是赋到j里面。
我们首先把父结点的这个值存下来，那这个下面的操作我们就是说
先找这个i结点它的左右
孩子里面最小的那一个，那因为我们刚才左孩子已经放在j里面了
就因此如果j++的那一位它比刚才j的那一位要
小的话呢那我们就下标就挪到就是j+1了那个位置。
好那我们把刚才那个position的当前位置
它的那个值跟我们
子孩子那里面的较小的值进行比较。如果是说
那个孩子的值更小，那么我们就需要
把它上升到刚才那个父结点的位置。
那实际上相当于是父结点SiftDown下来了一位。
然后我们接着这个下标也是
从这个树里面呢下降了一层，就是包括这个当前结点下标和它的
左子结点的下标，然后我们继续下一次的这样的循环操作。
那么这个操作我们在什么时候停止呢？也就是说如果在某一个位置
它的这个子结点的值比它呢
都要大，那就可以停止。或者是说一直到了叶层
那我们没有可以再往下头SiftDown的空间了，也是停止。
那这个停止位其实就落在了这个i位，然后我们前面保存过
那个最开始要调整的position位的那个数值就回填到i位。
所以我们这个SiftDown的这个操作其实我们跟刚才的动画里面的一个交换
是不太一样的，其实因为整个这个SiftDown的过程它是从position开始到某一位
截止，然后这一个序列过程它是连续的进行值的交换。
那因此其实我们就找到最后那一个位置，然后中间都是
往上头填就是下位置嘛往上头填，然后那个最前头的position位置最后落到
我们的一个目标位置就行了。好那类似的有SiftUp的一个
向上调整的操作，那么这个比刚才的SiftDown
更简单。因为父指针呢它是更容易查找的。
而且只有一个父，因此就是说当父子逆序的时候
在最小堆里面也就是说父结点的值它还大于子结点的值的时候
我们就是把这个子结点SiftUp上去。
那我们来看一下
建最小堆的这个过程。这N个
元素它其实是跟你的这个输入的情况
一样，然后就直接放到这个一维数组里头。
然后我们再来进行一个调整。那有两种思考的方法来调整建堆。
一种方法就是我们可能从上面开始来想。
自顶向下来想。那这个是不太容易想的，因为
我们的这个堆它的约束就是说他自己要
小于等于这个左右的子结点。但是再往下头这个约束
可以是比较混乱不好调整的。那我们如果是从底向上来调整的话
那就比较好想了，也就是说这里面大概有一半的元素它是已经自成为子堆。
然后我们找到第一个
它有孩子的这种节点，然后它跟它的左右子孩子进行一个
调整，就建成一个子堆。然后从这个大概二分之一的位置开始做这个事情。
一直往根的方向调整，那么就是逐步的调整
建立越来越大的这么一个最小堆。
好那我们看一下这个示例
大概这个68，05，16，94都不需要调整。然后从23开始
它也是已经成为子堆了。那71它跟这个里面更小的05进行一个调整。
那接着调73，那是一个类似的过程，那73呢你可以看到
它是个连续SiftDown的这样的一个结果。
那最后到根的时候因为它的左右的子树都已经是子堆了
那我们很方便的把它根SiftDown
到位以后，整个这个结构它就已经是最小堆了。
那我们看一下
相关的这个代码。这个代码其实非常简单，
也就是说，我们大概从1/2元素的这个位置开始，然后往根的方向上推进，
那每一次在这个相应的下标位，进行SiftDown的一个操作，
然后就完成了。那我们看一下这个
插入的算法，那也相对比较简单。插入的话呢首先我们要考虑，
这在堆里面我们不能够随便就往里面插，那我们往往是，
如果有一个新元素，那我是插到堆里面的
最后面那个元素之后的空位，然后，这个空位因为它是已经是在叶结点层，那它是不是
在堆里面是一个合法的位置呢？那我就跟它的父节点进行比较，
然后就是一个SiftUp的过程，就是一直调整到
它自己呆在一个合适的位置，那这就是这个算法的代码。
那我们看一下这个比较复杂一些的最小堆里面删除某一个元素
的操作。那这个删除某个元素，也是在某一个规定的一个下标位。
那如果这个下标位是在合理的范围之内的话，那首先我们是
跟这个下标位里面的最后那一个元素
进行交换，就是拿当前这个position跟那个最后的元素进行交换，
然后，交换到这个相应的位置以后，我们再来看，最后的那个元素呆在那个位置
的时候，它到底是应该SiftUp还是应该SiftDown。
其实这两个操作只可能进行一次，也就说要么SiftDown，要么SiftUp。
好，那我们来看这样一个例子，就是在这个堆里面，我们
删除68，那这是一个最小堆，那我们首先拿最后这个元素45来替换它，
然后45我们上下看一下，它到底是SiftDown还是SiftUp，它显然是SiftUp。
然后SiftUp以后就完成，可以看到它显然，如果SiftUp，它不需要再SiftDown。
那我们再来看删除16，那16也是拿45去替换这个16，
然后，我们再来看，它是应该SiftDown的，
那就是跟这个子的
根结点里面的较小的那个交换，然后看一下是不是还需要继续的SiftDown，那这里直到叶就完成了。
那建堆的效率是非常高的，因为我们
看到这n个元素的堆里面，大概有一半的元素是不需要移动的。
然后，有1/4的元素，顶多移动一次，
那每往上一层，元素的个数是减半，
而我们移动的次数只是增加1，
因此，它这个元素移动的最大的这样的
次数的总和，就会是这样一个数值。
那这个数值，我们算出来的结果就是O(n)的。对于n个
元素，我可以给你是杂乱无章的，然后你在一个线性的时间内，
就能够完成一个建堆的过程。那是相当高效的一种操作。
那因为堆有log n
层，然后我们前面看到插入删除操作，它实际上都非常的
局部，也就是涉及到这些元素的，它在
从它到根的路径上，或者是从它到叶的这个
路径上的某一些元素的一些交换，所以是非常局部的。
这个交换，它不可能超过树高，因此它们的时间代价呢，都是log n的。
堆可以用来实现优先队列。那我们在操作系统啊等等，很多
应用里面可以看到，我们比如说进程啊有优先级，然后还有些作业表有些优先调度这样的事情。
那我们在管理优先队列的时候，其实很多时候我们
最关心的是，谁最小或者是谁最大，要先出来先得到服务。
那优先队列，还有些相应的变种，不一定都是我们这里用完全二叉数实现的堆。
另外，如果我们需要改变优先队列里面的这些对象的
优先权的时候，那就需要有一些辅助的数据结构对它进行索引，先找到，然后再修改，再调整这个优先队列。
我们给大家留一下思考题，也就是说，刚才我们动画的
就是SiftDown的时候，实际上是，一旦发现
逆序对，就会交换的。但是我们在编写算法的时候不是的。我们是
先把那个该处理的元素，腾到一个临时变量里面。然后
这个SiftDown的操作，其实是一系列的过程。然后我们其实是把
后面这个元素是往上头推了一下，然后最后就是应该达到的那个目标位置，
我们再把那个前面position，需要处理的那个元素给它定位，落到那个目标位置。
那我们如果要改写，你怎么改写一下？还有就是，我们是不是能够在一个
数据结构里面，同时维护最大值和最小值？实际上是有这样的数据结构的，
就是最大最小堆，大家可以去查阅一下。谢谢。