II. Mergeable Heaps

Leftist Heap

空路径长度(null path length)：$Npl(X)$ 定义为从节点 $X$ 任意没有两个孩子的子节点的最短距离。特别地，定义 $Npl(\text{NULL})=-1$，对于叶子节点或只有一个孩子的子节点，其 $Npl$ 显然为 $0$。显然有：

$$Npl(X)= 1+\min\{Npl(C) \mid C \text{ is a child of } X\}$$

左倾堆(leftist heap)：对于左倾堆的每个节点，其左节点的 $Npl$ 值大于等于右节点的 $Npl$ 值。

Operations

Merge

递归合并，每次插入到右侧。插入后如果右子树的 $Npl$ 更大则交换左右子树。

也有一种不“交换”左右孩子的方法，定义一个 $rc$ 函数每次根据左右孩子的 $Npl$ 返回 $Npl$ 较小的店作为右节点即可。

Insert

看做与一个单节点的子树合并。

DeleteMin

删去根，合并根节点的两个子树。

Complexity Analysis

TBD

Skew Heap

斜堆(Skew Heap)，也叫做自适应堆(self-adjusting heap) 是另一种可并堆，它不需要记录任意一个节点的距离，只是在合并操作上有所改变。

Operations

Merge (Recursive)

• 比较两个堆；设 $p$ 是具有更小的 $root$ 的键值的堆，$q$ 是另一个堆，$r$ 是合并后的结果堆。
• 根据堆性质，选 $p$ 的根节点作为 $r$ 的根节点。
• 令 $r$ 的右子树为 $p$ 的左子树。
• 令 $r$ 的左子树为 $p$ 的右子树与 $q$ 合并的结果。

Merge (Non-recursive)

• 把每个堆的每棵（递归意义下）最右子树切下来。这使得得到的每棵树的右子树均为空。
• 按 $root$ 的键值的升序排列这些树。
• 迭代合并具有最大 $root$ 键值的两棵树：
  • 具有次大 $root$ 键值的树的右子树必定为空。把其左子树与右子树交换。现在该树的左子树为空。
  • 具有最大 $root$ 键值的树作为具有次大 $root$ 键值树的左子树。

Complexity Analysis

重节点(heavy node)：称一个节点 $p$ 是 heavy 的，当且仅当它右子树的节点数大于等于左子树的节点数。

进行均摊分析，定义势能函数

$$\Phi(D_i) = \text{the number of heavy nodes}$$

考虑第 $i$ 次合并过程，它们右路径上的轻重节点个数分别为 $l_p,\ h_p$ 和 $l_q,\ h_q$。则一次合并的实际代价为

$$c_i = l_p+ l_q+h_p+h_q$$

另外注意到，一次操作后，重节点一定变成轻节点，但是轻节点不一定变成重节点。这是因为

• 对于一个重节点，原先较大的右子树交换到右侧且会与另一棵树合并，从而变得更大，故重节点合并后一定变成轻节点。
• 对于一个轻节点，虽然较重的子树被换到右侧，但是由于左子树和另一个树合并可能变得更大，故合并后有可能是轻节点也有可能是重节点。

故势能增加量

$$\Phi(D_{i+1}) - \Phi(D_i) \leq l_p+l_q-h_p-h_q = O(\log N)$$

而右路径上的轻节点的数是 $O(\log n)$ 级别的，所以总复杂度为 $O(n\log n)$。

Binomial Queue

二项堆(binomial queue)：A binomial queue is not a heap-ordered tree, but rather a collection of heap-ordered trees, known as a forest. Each heap-ordered tree is a binomial tree.

二项树(binomial tree)：A binomial tree of height $0$ is a one-node tree. A binomial tree, $B_k$, of height $k$ is formed by attaching a binomial tree, $B_{k-1}$, to the root of another binomial tree, $B_{k-1}$.

Observation

$B_k$ consists of a root with $k$ children, which are $B_0,B_1,\ldots B_{k-1}$. $B_k$ has exactly nodes. The number of nodes at depth $d$ is $\displaystyle\binom{k}{d}$.

注意到二项树有以下重要性质：

• 二项树 $B_k$ 的总结点数是 $2^k$，这意味着我们想要构建一颗大小为 $n$ 的二项堆时，可以对 $n$ 进行二进制拆分。
• 二项树的合并是简单的，可以通过两个 $B_{k-1}$ 通过 $O(1)$ 的复杂度直接得到 $B_k$，并且维持堆性质不变。

Operations

FindMin

枚举 binomal queue 中的每个堆，取他们的根节点的最小值。由于 binomal queue 中的堆的数量是 $O(\log n)$ 的，故这一操作的复杂度为 $O(\log n)$。

Merge / Insert

可以类比二进制数的竖式加法，来确定需要按照什么样的顺序将哪些 binomal trees 合并，这里别忘了要考虑进位。

DeleteMin

找到根节点值最小的 binomal tree，设为 $B_{k-1}$ 将其根节点删除，其孩子应分别为 $B_0,B_1,\cdots,B_{k-1}$，将这些孩子视为另一个 binomal queue，和原 binonal queue 删除 $B_k$ 后的结果合并，应用上面的 Merge 算法即可。

Implementation

实现时为了方便快速实现孩子的顺序遍历，在存储孩子时可以考虑使用链表的方式，或者说，使用左儿子右兄弟(left-child , right-sibling) 的连接方式。

另一方面，我们的链表最好按照 $B_{k-1},B_{k-2},\cdots,B_0$ 的方法存储这些数，这样在合并的时候不用遍历孩子链表也能维持左儿子有兄弟的结构，具体自己画个图就知道了。

Complexity Analysis

Claim

A binomial queue of $n$ can be built by $n$ successive(连续) insertions in $O(n)$ time.

可以用均摊分析证明，具体证明过程略。

$$\begin{aligned} c_i &::= \text{cost of the }i\text{th insertion.}\\ \Phi_i &::= \text{number of trees after the }i\text{th insertion } (\Phi_0=0) \end{aligned}$$