堆¶
左倾树¶
左偏树，也叫左倾堆 (Leftist Heap) ，是一种二叉堆，和普通的堆有一样的顺序性质，但是不要求平衡，可以很快地完成合并操作。
对每个节点定义一个零距离 (Null Path Length, NPL)，即节点到最近的外部节点的距离，其中外部节点为没有两个子节点的节点。空节点的零距离为 -1，然后可以递归地得到其他节点的零距离：
左偏树的性质是：对于任意节点，它的左儿子的零距离大于等于右儿子的零距离。因此 \(NLP(x) = NPL(x.\text{right}) + 1\)。
合并¶
以小根堆为例，递归地合并两个左偏树的步骤如下：
- 若有一个为空，则返回另一个
- 比较两个根节点，将较小的根节点作为新根节点，保持新根节点的左子树不变，然后递归地合并其右子树与另一个左偏树，作为新根节点的右子树
- 若合并后不满足左偏性质，则交换左右子树
迭代地合并两个左偏树的步骤如下：
- 用两个指针分别指向两个左偏树的根节点，取出较小的一个作为新根节点，然后向右儿子移动对应指针
- 不断取出两个指针指向的节点中较小的一个，作为上一个取出节点的右儿子，然后向右儿子移动对应指针，直至指针为空
- 从最后一个取出的节点开始，不断调整左右子树以满足左偏性质，向上直至根节点
插入与删除¶
插入：将单个节点视为一个堆，合并到原堆即可中。
删除：将根节点删除，然后合并左右子树即可。
分析¶
定理：设右路径为从根节点开始一直往右走的路径，一个右路径包含 \(r\) 个节点的左偏树最少有 \(2^r - 1\) 个节点。
用数学归纳法证明：对于一个右路径节点数为 \(k+1\) 的左偏树，其右子树的右路径节点数为 \(k\)，由 \(NLP(x) = NPL(x.\text{right}) + 1\) 和 \(NPL(x.\text{left}) \ge NPL(x.\text{right})\) 可得其左子树的右路径节点也应至少为 \(k\)，从而得该左偏树至少有 \(2^k - 1 + 2^k - 1 + 1 = 2^{k+1} - 1\) 个节点。
因此，一个有 \(n\) 个节点的左偏树的右路径节点数至多为 \(\log(n+1)\)。而上述操作均基于右路径进行，因此左偏树各操作的时间复杂度为 \(O(\log n)\)。
斜堆¶
斜堆 (Skew Heap) 是一种二叉堆，与左偏树类似，但是不需要用到零距离，每一步都交换左右子树，除了右路径中最大的那个节点。斜堆的优点是不需要额外的空间来存储零距离，而且也不需要判断是否应该旋转。
斜堆的均摊时间复杂度也为 \(O(\log n)\)，可以通过势能分析来证明。
首先定义一个节点是重节点 (Heavy Node) 当且仅当其右子树的节点数大于左子树的节点数，否则就是轻节点 (Light Node)。然后定义势能函数 \(\phi\) 为两个斜堆的重节点总数，\(h\) 为两个斜堆除右路径外的重节点总数，\(l_1, l_2\) 为两个斜堆右路径上的轻节点个数，\(h_1, h_2\) 为两个斜堆右路径上的重节点个数。
这样以后，易得合并两个斜堆的实际代价为 \(c = l_1 + h_1 + l_2 + h_2\)，在合并前的势能为 \(\Phi_0 = h_1 + h_2 + h\)。
现在来看合并之后的重节点个数。因为右路径之外的重节点的儿子不会发生变化，因此 \(h\) 是不变的。而在原右路径上的重节点，在交换前，其左子树节点数不变，右子树节点数要么不变要么变大，因此在交换后必然变为轻节点，从而有 \(\Phi_N = l_1 + l_2 + h\)。
因此合并操作的均摊代价为 \(c + \Phi_N - \Phi_0 = 2(l_1 + l_2)\)。
现让我们构造一个让右路径上的轻节点尽可能多的斜堆，在这个斜堆上，右路径上的每一个节点一方面需要让左子树节点多于右子树节点，另一方面需要让右子树节点数尽可能地多，以增长右路径，因此右路径上的每一个节点需要让左子树和右子树节点数相同，从而可得 \(l = O(\log n)\)，因此合并操作的均摊复杂度为 \(O(\log n)\)。
二项队列¶
尽管左倾树和斜堆实现了 \(O(\log N)\) 复杂度的插入操作，但是无法像普通堆一样，实现 \(O(N)\) 复杂度的建堆操作，因此需要引入二项队列。二项队列是一组堆有序的二项树的集合，这里以最小优先队列为例。
定义只有一个节点的二项树的高度为 0，记为 \(B_0\)；高度为 \(k\) 的二项树由两个高度为 \(k-1\) 的二项树合并而成，以其中的较小的根节点为新的根节点，记为 \(B_k\)。这样以后，可得二项树有如下性质：
- \(B_k\) 的根节点有 \(k\) 个儿子，分别为 \(B_0, B_1, \cdots, B_{k-1}\)
- \(B_k\) 有 \(2^k\) 个节点
- 深度 \(d\) 的节点数为 \(\begin{pmatrix} k \\ d \end{pmatrix}\)
所有数字都可以表示为唯一的二进制数，因此给定固定长度的二项队列，其中有无 \(B_k\) 是确定的。
因为二项树的儿子节点数是不定的，且没有随机访问儿子节点的需求，因此此处使用左儿子右兄弟的表示法。
合并¶
在合并两个二项树时，可以直接将根节点较大的二项树置为另一个二项树的左儿子，这样就能以极小的代价保证 \(B_k\) 根节点的所有儿子以 \(B_{k-1}, \cdots, B_1, B_0\) 的顺序排序，有利于后续删除操作。
在合并两个二项队列时，可以将这个过程看作两个二进制数相加的过程，进位的过程就是合并二项树的过程。若进位后有三个 \(B_k\)，此时可以为了方便直接合并原有 \(B_k\)，也可以选择合并其中根节点最大的二项树和另一个二项树，以使那个最大的根节点不再是根节点，有利于加快查询最小值的操作。
插入与删除¶
插入操作即为将一个元素看作一个二项队列，然后与原有二项队列合并。
删除操作即为将最小元素所在的二项树的根节点移除，将该根节点的所有儿子视为新的二项队列，将其与其余二项树合并。
分析¶
易得查询最小值的复杂度为 \(O(\log N)\)，合并二项树的复杂度为 \(O(1)\)。因此，合并二项队列的复杂度为 \(O(\log N) \times O(1) = O(\log N)\)，插入和删除操作的最坏时间复杂度是 \(O(\log N)\)。
现考虑从零开始逐个插入元素的情况：
聚合法：因为只有进位时才会进行合并二项树操作，而从最低一位开始，在对应位置发生进位需要的插入次数依次为 2、4、8、...，因此最终合并二项树的次数为 \(\frac{N}{2} + \frac{N}{4} + \cdots = N\)，总的建堆时间复杂度为 \(O(N)\)。
势能法：定义势能函数为二项树的数量，实际代价为合并次数加一，则当 \(c_i = c\) 时，\(\Phi_i - \Phi_{i-1} = 1 - (c - 1) = 2 - c\)，因此均摊代价 \(\hat{c}_i = 2\)，总的建堆时间复杂度为 \(O(N)\)。