黑马程序员技术交流社区

标题: 探秘堆结构 [打印本页]

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

作者: static小白 时间: 2016-5-13 22:39
没看懂，好高深啊

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2