C语言之算法与数据结构系列之探秘堆结构！

一、概述

此处所说的堆为数据结构中的堆，而非内存分区中的堆。堆通常可以被看做是树结构，满足两个性质：

1）堆中任意节点的值总是不大于（不小于）其子节点的值；

2）堆是一棵完全树。正是由于这样的性质，堆又被称为优先队列。根据性质一，将任意节点不大于其子节点的堆称为最小堆或最小优先队列，反之称为最大堆或最大优先队列。优先队列在操作系统作业调度的设计中有着举足轻重的作用。之前写了一篇优先队列的文章，详见算法导论第六章优先队列。

常见的堆结构，有二叉堆、左倾堆、斜堆、二项堆、斐波那契堆等。斐波那契堆在前文算法导论第十九章 斐波那契堆已经作了讲述。本文主要对其余几种堆结构做宏观上的概述，并说明它们的异同点。

二、二叉堆

二叉堆是最简单的堆结构，本质是一棵完全的二叉树，一般由数组实现，其父节点和左右子节点之间存在着这样的关系： 索引为i（i从0开始）的左孩子的索引是 (2i+1); 右孩子的索引是 (2i+2); 父结点的索引是 floor((i-1)/2)。详细请看我之前写的一篇文章：算法导论第六章堆排序（一）。众所周知，二叉堆在排序算法中应用甚广，特别是涉及到大数据的处理中，如Topk算法。

三、二项堆

某些应用中需要用到合并两个堆的操作，这个时候二叉堆的性能就不是很好，最坏情况下时间复杂度为O(n)。为了改善这种操作，算法研究者就提出了性能更好的可合并堆，如二项堆和斐波那契堆，当然还有左倾堆，斜堆等。二项堆对于该操作能在最坏情况Θ(lgn)下完成，而斐波那契堆则更进一步，能在平摊时间为Θ(1)下完成（注意是平摊时间），见下表。除了Union操作，二叉堆各操作的性能都挺好，而二项堆对此也仅仅是改善了Union操作，对于Minimum操作甚至还不如二叉堆，我想这大概是《算法导论》第三版没有把二项堆再作为一章的原因之一吧。而斐波那契堆各个操作都有极好的性能，除了Extract_min和Delete操作。

说回到二项堆，二项堆是由一组的二项树组成，二项树B_k是一种递归定义的有序树，其具有以下的性质：

1）共有2^k个节点；

2）树的高度为k；

3）在深度 i 处恰有C^i_k个节点，因为C^i_k为二项系数，正因如此，才称其为二项树；

4）根的度数为k（即孩子节点个数），它大于任何其他节点的度数。

二项树B_0只包含一个节点，二项树B_k由两棵二项树B_k-1连接而成，其中一棵树的根是另一棵树的根的最左孩子。如下图：

二项堆H由一组满足下面二项堆性质的二项树组成：

1）H中的每个二项树满足最小堆性质（说明二叉堆中最小节点在二项树的根中）；

2）对任意非负整数k，H中至多有一棵二项树的根具有度数k（说明在包含n个节点的二项堆中，至多有floor(lgn)+1棵二项树）。

不同于斐波那契堆采用双循环链表来连接根节点和孩子节点，二项堆中采用的是单链表，每个节点有指向父节点的指针，孩子节点指针和兄弟节点指针，如：

下面列上自己写的动态集合操作的代码：

关于怎么快速学C/C++游戏编程，有什么方法，这个问题，想必大家都已经心中有数了，打算深入了解这个行业的朋友，可以加下小编的C/C++游戏编程学习裙:四五三 + 二四三 + 二八零，不管你是小白还是大牛，小编我都欢迎，不定期分享干货，包括小编自己整理的一份2018最新的C/C++资料和0基础入门教程，欢迎初学和进阶中的小伙伴。

四、左倾堆

左倾堆（leftist tree 或 leftist heap），又称为左偏树。这种结构《算法导论》上没有提及，大概是因为太简单了吧。因为其本质是一棵二叉树，不像二项堆和斐波那契堆一样，具有复杂的结构。我想历史的演进过程大概是先提出左倾堆以及接下来要说的斜堆，然后才提出的二项堆和斐波那契堆这种复杂的结构，由易到难嘛，又或者同时，相反，anyway。

二叉堆是非常平衡的树结构，左倾堆，从名字上来看，这种堆结构应该是整体往左倾，不平衡，那是什么导致它往左倾，孩子节点个数？不可能，比如下面这棵树：

如果只从孩子节点个数来评判它往哪倾，则从整体上看，根节点的右孩子节点要多于左孩子节点，但是这棵树是左倾堆。那到底通过什么来评判一棵树为左倾堆？要引入一个属性：零距离（英文名NPL，Null Path Length）——表示的是从一个节点到一个“最近的不满节点”的路径长度（不满节点：两个子节点至少有一个为NULL）。一个叶节点的NPL为0，一个NULL节点的NPL为-1。因此，左倾的意思主要是看每个节点的NPL是否满足左孩子的NPL >= 右孩子的NPL，这也是左倾堆的性质一。当然啦，左倾堆既然叫堆，自然满足堆的性质：即每个节点的优先级大于子节点的优先级，这是性质二。还有性质三就是：节点的NPL = 它的右孩子的NPL + 1。如上图：每个节点旁边的标号即为它们的NPL值。

如前所述，这些堆结构的提出，主要是解决简单二叉堆中Union操作的低性能的。左倾堆的Union操作相对上述两种比较简单，基本思想如下：

1）如果一个空左倾堆与一个非空左倾堆合并，返回非空左倾堆；

2）如果两个左倾堆都非空，那么比较两个根节点，取较小堆的根节点为新的根节点。然后将“较小堆的根节点的右孩子”和“较大堆”进行合并；

3）如果新堆的右孩子的NPL > 左孩子的NPL，则交换左右孩子；

4）设置新堆的根节点的NPL = 右子堆NPL + 1。

上面的Union算法递归调用了自身，由于我们沿着右侧路径递归，所以时间复杂度为lgn量级。至于其他操作，比如insert，delete_min都可以在Union的基础上实现，如insert：将新增节点与一个已有的左倾堆做Union；delete_min删除根节点，将剩余的左右子堆合并。具体的就不再详述，如有疑问，可以参考这篇图文并茂的博客：左倾堆(一)之 图文解析 。（站在别人的肩膀上学习，避免重复造轮子^-^）

五、斜堆

斜堆（skew heap），又称自适应堆，它是左倾堆的一个变种。相比于左倾堆，斜堆的节点没有“NPL”这个属性，合并操作也相对简单了，但同样能实现lgn的量级。具体算法过程的前两步和左倾堆是一样的，只是第三步不像左倾堆要比较左右孩子的NPL大小才交换，而是合并后就直接交换。

六、总结

最常用的堆结构还是要属二叉堆，前面也提到过，如果没有Union操作，二叉堆的性能还是令人满意的。对于一些复杂的问题场景，则相应需要用到复杂的数据结构，此时斐波那契堆是最佳选择，如求最小生成树问题和求单源点最短路径问题的实现，如果基于斐波那契堆，则能得到非常好的性能。但这只是从理论上来说，《算法导论》上也说了，如果从实际应用角度来看，除了某些需要管理大量数据的应用外，对于大多数应用，斐波那契堆的常数因子和编程复杂性使得它比起普通二叉堆并不那么适用。因此，斐波那契堆的研究主要出于理论兴趣。这个时候，如果权衡一下，那就只有左倾堆和斜堆这等堆结构更适用了。是这样吗？不禁陷入了深深的思考中……