# 高级数据结构II

## 二项堆

1. 可合并的堆

2. 二项树：递归定义，$B_0$ 是单个节点，$B_k$ 由两棵 $B_{k-1}$ 树根相连而成，根节点的高度为 $k$，有 $2^k$ 个节点，第 $m$ 层有 $C_k^m$ 个节点

3. 二项堆：由多个二项树组成，每个二项树的根节点的度数互不相同，且每个二项树都是最小堆

4. 二项堆性质
   - 最小值在根链上
   - $N=\sum_{i=0}^{\lfloor\lg N\rfloor}b_i2^i$
   - 最多有 $\lfloor\lg N\rfloor+1$ 棵二项树
   - 高度最多为 $\lfloor\lg N\rfloor$

5. 二项堆的合并：因为一个二项堆的每种度数节点二项树只出现一次，因此可以用二进制数来表示某度数节点二项树是否出现，两二项堆合并只需类似对应的数相加即可得到对应代表的二项堆，时间复杂度为 $O(\lg n)$

6. 二项堆删除最小值：在根链上删除最小值，将删除节点子节点形成的二项堆与原二项堆合并，时间复杂度为 $O(\lg n)$

7. 二项堆将某个节点减小：如果太小要将该节点向上移，时间复杂度 $O(\lg n)$

8. 二项堆删除节点：将对应节点减小至 $-\infty$，然后删除该最小值

## 斐波拉契堆

1. 摊还时间分析
   - 如果有一个操作重复很多次，可以在第一次前做一些处理，使得之后的每次操作快很多，而这些处理的时间复杂度应该平摊给之后的多次操作，使得时间复杂度相比不做处理时更快

2. 斐波拉契堆只在删除最小值及调用删除最小值来删除某个节点时所需的时间复杂度为 $O(\lg n)$，而其他操作均为摊还的 $O(1)$

3. 斐波拉契堆的思想
   - 和二项堆类似，但没有那么严格
   - “懒”合并，摊还

4. 斐波拉契堆是一些最小堆序树的集合
   - 其中的每个节点都有一个指针指向其父节点，有一个指针指向每个子节点，且每个节点都和兄弟节点组成双向循环链表
   - 树根节点组成一个双向循环链表，称为根链表
   - 同时有个指针指向最小值节点
   - 节点上有一个字段记录其度数
   - 存在一些节点被标记
   - 整个斐波拉契堆要记录节点的最大度数 $D(n)$，树的个数 $t(H)$，标记节点的个数 $m(H)$，以及势函数 $\Phi(H)=t(H)+2m(H)$

5. 插入
   - 创建一个只有一个节点的树，插入到根链表中最小节点的左边，如果该节点的值比最小值小，则更新最小值指针
   - 时间复杂度 $O(1)$

6. 合并
   - 将两个斐波拉契堆的根链表在最小值指针处合并，并更新最小值指针
   - 时间复杂度 $O(1)$

7. 删除最小值
   - 删除最小值节点，且将其子节点合并进根链表
   - 将根链表中度数相同的节点合并，使得根链表中每个度数的节点只有一个；合并使用一个数组进行辅助，只需扫描一遍根链表即可
   - 实际时间复杂度为 $O(D(n)+t(H))$，摊还时间复杂度 $O(D(n))$

8. 将某个节点值减小
   - 若没有影响最小堆的性质，则只需要减小该节点值，并更新最小值指针即可
   - 若影响了最小堆的性质，且节点父节点未被标记，则减小节点值后将节点从其父节点上分离，插入到根链表中，更新最小值指针，并将原父节点标记
   - 若影响了最小堆的性质，且节点父节点被标记，则减小节点值后将节点从其父节点上分离，插入到根链表中，更新最小值指针；再将原父节点从其父节点上分离，取消标记，插入到根链表中，更新最小值指针；并递归处理原父节点的父节点
   - 实际时间复杂度为 $O(c)$，$c$ 为级联删除的次数，摊还时间复杂度 $O(1)$

9. 删除
   - 将一个节点减到无穷小，并调用删除最小值的操作
   - 摊还时间复杂度 $O(D(n))$

10. 分析
   - **关键引理**：在斐波拉契堆中，$D(n)\leqslant\log_{\phi}n$，其中 $\phi=\frac{1+\sqrt{5}}{2}$
      - 斐波拉契数列 $F_0=0,F_1=1,F_k=F_{k-1}+F_{k-2}$，则有 $F_{k+2}\geqslant\phi^k$
      - 引理：$x$ 是一个度数为 $k$ 的节点，$y_1,\ldots,y_k$ 为 $x$ 的子节点，且以合并的顺序为下标，则 ${\rm degree}(y_i)\geqslant \max(0,i-2)$；因为 $y_i$ 加入进来时，度数为 $i-1$，但可能会被删掉一个子节点，因此度数至少为 $i-2$
      - 要证明关键引理只需证明 ${\rm size}(x)\geqslant \phi^{{\rm degree}(x)}$，因为这样就有 ${\rm degree}(x)\leqslant \log_{\phi}{\rm size}(x)\leqslant\log_{\phi}n$
      - 令 $s_k$ 为以度数为 $k$ 节点为根的树的最小规模，则有 $s_0=1,s_1=2$，则有 $s_{i-2}\geqslant F_i,i\geqslant 2$
      - 因此 ${\rm size(x)}\geqslant s_k\geqslant 2+\sum_{i=2}^ks_{{\rm degree}(y_i)}\geqslant 2+\sum_{i=2}^kF_i=F_k+2\geqslant\phi^k$

## 不相交集合/并查集

1. 不相交集合：一些互不相交的集合，每个集合中可能有多个不同的元素，支持集合合并与查找

2. 链表的表示，合并将小的集合合并到大的集合中

3. 树的表示，合并将矮树合并到高树中，查找中加入路径压缩的方法
