文章目录 1. LeftHeap模板类2. 算法3. 实现4. 实例 1. LeftHeap模板类 接下来这节，来讨论左式堆的合并算法。再给出具体算法之前，首先要给出左式堆模板类的定义。 比如这就是一种可能的实现方式，可以看到，我们这里再次利用了 C++的多重继承，只不过与完全二叉堆不同，既然左式堆已经不再满足结构性，所有元素在物理上也不可能继续保持紧密的排列，因此继续从向量

文章目录 1. 第一印象2. 堆之合并3. 奇中求正4. NPL5. 左倾性6. 左展右敛 1. 第一印象 在学习过常规的完全二叉堆之后，我们再来学习优先级队列的另一变种，也就是左式堆。所谓的左式堆，也就是在拓扑形态上更加倾向于向左侧倾斜的一种堆， 比如这就是一个左式堆由生到长，直至灭亡的整个生命过程。 可以看到，相对于常规的完全二叉堆，左式堆的确显得有些别致。 那么，为什

数据结构之左式堆 左式堆 概念： 左式堆是一种能够高效的支持合并操作的堆，左式堆的底层也是由二叉树实现，但是左式堆不是平衡的(不由完全二叉树实现的)，左式堆趋向于不平衡。左式堆也像二叉堆一样拥有着堆的特性(有序性和结构性)，左式堆是最小堆左式堆是一个拥有堆序性的二叉树(不是二叉堆)加上NPL特性的一棵树，任意节点X的NPL(X)(零路径长)为从X到一个没有两个儿子的节点的最短路径的长，因此，

堆合并 堆合并是指，对于任意两个堆，将其合并为一个更大的堆，如下图所示： 为了解决这个问题，我们可以首先进行一些初步的尝试。 简明的插入策略 最简明的思路，无非是将一个堆中的元素，逐个删除并且依次插入到另一个堆中。不妨设两个堆的规模分别为m和n，则这种策略的时间复杂度为O(m * (logm + log(m + n))) = O(m * log(m + n))。 Floyd批