看图说话之二叉堆(优先队列)——原理解析

一丶优先队列简介

    优先队列更多的是一种逻辑上和业务上的设计。队列中的每项元素都分配一个优先权值，队列的出队顺序按照优先权值来划分，高优先权先出队或者低优先权先出队。这样一个优先队列必须具备两个最基本的操作——入队，以及高(低)优先权出队。优先队列在很多场景中都有运用，比如打印机的任务调度和操作系统中的进程调度都有用到优先队列的设计。

图1 优先队列的两个基本功能

    此时我们假设并不知道有堆这样的数据结构，想实现上述这样的功能，其实也可以有多种解决方案，比如以下两种：

• 构建一个链表操作，入队操作等效于在表头以0(1)的时间完成插入操作，出队操作等效于遍历链表删除最大(最小)节点时间消耗在O(N)。这样的设计保证入队操作是常数，出队操作是线性。

• 构建一个链表，插入的过程中，始终保持链表是有序排列的(插入排序)，这样入队操作的时间消耗是0(N),出队操作，就是删除链表头元素，时间消耗为0(1)。
      假如采用这种设计，入队操作多于出队的情况下选择(1),反之选择(2)。此时注意到，无论是哪种设计，入队/出队总有一个操作是线性时间消耗，在大数据的条件下，设计一种更加高效率数据结构完成优先队列的设计主必要的——二叉堆就是以O(logn)的时间复杂度完成出队和入队操作的优先队列设计。下面详细的介绍堆这种数据结构的原理和实现

二丶二叉堆的性质

    二叉堆如其名字一样和二叉树具有紧密的关系。二叉堆是一种特殊的二叉树，是对一般的二叉树提出了结构性和堆序性的要求，这种特殊结构性和堆序性是二叉堆的性质所在。

1.结构性：二叉堆是一个完全二叉树

2.堆序性：所有的节点值均小于(大于)其后裔节点值，若所有节点值大于其后裔节点这样的二叉堆称为大根堆##点值均小于其后裔节点这样的二叉堆成为小根堆。

图2 小根堆
图3大根堆

    这里可以看到，假如是小根堆的情况，那么每次取堆顶的元素，就完成了按低优先级出队的功能。若是大根队取堆顶的元素则完成按高优先级出对的顺序。
    这里需要特别注意就是，每次的出队操作=返回堆顶元素+删除堆顶元素，每次删除堆顶元素之后，需要保证依旧满足二叉堆的结构性和对堆序性，这个删除和调整的过程称为堆调整。
    下面以大根堆为例进行介绍一次堆调整，并且分析其时间复杂度为什么是O(logN)。下文描述中，堆的删除操作=优先队列的出队，堆的插入操作=优先队列的入队。

三丶大根堆的出队操作

1. 拷贝堆顶元素，此时拷贝后的堆顶元素即为最后出队将返回为元素。

   
   图4 拷贝出队元素

2. 二叉堆，删除一个元素后，堆顶的位置就空闲下来了，同时需要保持二叉堆的结构特性不变，所以二叉堆最后一个元素必须要移动，而且堆顶的空闲必须要被填补。最简单做法就是利用二叉堆的最后一个元素去填补堆顶的元素，结果如图

   
   图5堆尾元素填补堆顶。

3. 观察图5此时的二叉堆情况，可以发现二叉堆的结构特性已经满足了，但是其堆序特性被破坏了。元素6是小于其左节点10和节点15的，所以调整此时二叉堆的堆序是要处理的工作，比较自身节点值，左节点值，和右节点值，取三者中的最大值替代自身，结果如下图所示。

   
   图6第一次堆调整结果

4. 观察图6第一次堆调整完后的情况，可以发现元素6的左节点和右节点依然不满足堆序的特性。需要继续调整，调整方法如步骤3，调整结果如下图所示。

   
   图7第二次堆调整结果
5. 第二次调整后，发现元素6是叶子节点了，调整结束。此时观察图7的二叉堆发现此时不仅满足二叉堆的结构特性，同时所有的节点都满足了堆序的特性。
6. 最后将copy的出队值20返回，则完成了一次二叉堆的删除操作，同时也是一次优先队列的出队操作。

总结：

• 从上面步骤1到步骤6可以归纳出，删除操作的核心就是将堆尾的元素通过不断的堆调整，将其放置到合适的位置，以满足堆序特性。

• 堆尾的元素是在根节点通过一步步的比较，然后找到的合适位置，可以看到该元素是一层层的往下走，这个过程形象的称为“下滤”。

• 在上述的例子中下滤过程的结束是因为已经下滤到叶子节点了，除此之外如果在下滤的过程中发现其左右节点的值均小于自身(满足堆序特性)那么下滤过程同样结束。

• （4）.一次堆删除操作(出队)，是从根节点开始下滤，下滤过程中经过的路径长度决定时间的消耗，对于二叉堆来说，其是完全二叉树，若节点数为N，则高度不超过过logN,所以出队操作的时间消耗最大为O(logN)，即最坏时间复杂度。

四丶大根堆的入队操作

    上文介绍了大根堆的出队操作，其时间复杂度在O(logN),此处介绍大根堆的入队操作，入队操作和出队操作和其相似，最坏时间复杂度也是O(logN)。下面将通过图例的形式分析大根堆的入队操作，假设插入元素是19。

     图8 大根堆初始状况
1.在插入的过程中，也要保持结构性和堆序性，那么从结构性的角度来看，插入的元素19只能放在末尾，如下图所示。
图9 入队调整堆结构

2.如图9所示，在插入元素之后二叉堆的结构特性已经满足了，下面主要需要调整堆序特性。对于元素19而言，找到其父亲元素8，判断堆序性，发现19大于8，所以交换19和8的位置，结果如下。

图10入队调整堆序特性。
3.在经过上述的调整之后，发现元素19比其父亲元素大，依然不满足堆序特性，继续重复步骤2的堆序调整，结果如下：
图11 入队调整堆序特性
4.经过步骤2和步骤3的调整之后，发现19小于其父元素20了，已经满足堆序特点了，那么调整结束，此次入队操作完成。

总结：

• 二叉堆入队操作和二叉堆出队操作有很多相似的地方，二叉堆出队操作形象的描述为“下滤”，那么入队的操作从上述的过程中来看可以描述为“上滤”。

• 二叉堆的入队操作，上滤过程的起点是叶子节点，终点是根节点，所以其走过的路径依然是其主要的时间消耗，其走过的最大路径是二叉树的高度,所以其时间复杂度也是O(logN)。

Reference:
[1] 数据结构与算法 java语言描述版
[2] 博客原文