前言
研究一下堆。
什么是堆
堆是一种点带权的树，每个节点的权都小于/大于其父亲节点的权。
以下为了方便就只说小根堆了。
堆通常需要支持以下几种功能 ：
- 插入（insert）
- 查询最小值（min）
- 删除最小值 (extracy min)
- 合并（merge）
- 减小一个元素的值（decrease key）
二叉堆（Binary Heap）
结构最简单的堆，为一棵完全二叉树。
结构与维护
二叉堆结构采用堆式存储法，节点从 \(1\) 开始编号，则节点 \(x\) 的父亲是 \(\left\lfloor \dfrac{x}{2} \right\rfloor\)，两个子节点为 \(2x,2x+1\)。
维护的操作有两种：向上调整和向下调整。
向上调整就是不断将一个节点与其父亲节点交换，直到交换到根或者满足堆的性质（点权大于父节点权值），由于满二叉树树高是 \(\log n\)，这个操作的单次复杂度就是 \(\mathcal{O} (\log n)\)。
向下调整就是不断将这个节点与其两个子节点中权值最小的交换直到其成为叶子或者已经满足堆性质，复杂度同样 \(\mathcal{O}(\log n)\)。
查询最小值
小根堆堆顶元素即为最小值，复杂度 \(\mathcal{O}(1)\)
删除最小值
把堆顶元素与末尾元素交换，删除末尾，进行一次向下调整，复杂度 \(\mathcal{O}(\log n)\)。
插入
加入到末尾然后向上调整，复杂度 \(\mathcal{O}(\log n)\)。
减小键值
直接修改然后向上调整即可，复杂度 \(\mathcal{O}(\log n)\)。
合并
二叉堆不能快速合并，只能用启发式合并的思想优化一下时间复杂度。
建堆
直接复制原数组，然后从末尾对每个元素向下调整。
可以发现对于深度为 \(k\) 的节点进行一次向下调整实际是 \(\mathcal{O}(\log n - k)的\)。
于是整体复杂度就是 \(\mathcal{O}(n)\) 的了。
堆排序
首先建堆然后一直弹出最小值即可。
不用向下调整建堆的怎么能算是堆排序啊(恼)
代码
struct BinaryHeap {
int tot;
int T[N];
BinaryHeap() : tot(0) {}
inline void down(int p) {
for(int ch;(p << 1) <= tot;p = ch) {
ch = p << 1;
ch += (ch < tot && T[ch | 1] < T[ch]);
if(T[ch] <= T[p]) std::swap(T[ch],T[p]);
else break;
}
}
inline void up(int p) {
for(;p > 1;p >>= 1) {
if(T[p] <= T[p >> 1])
std::swap(T[p],T[p >> 1]);
else break;
}
}
inline void push(int x) {
T[++tot] = x,up(tot);
}
inline int top() {
return T[1];
}
inline void pop() {
T[1] = T[tot--],down(1);
}
void build(int *v,int n) {
tot = n;
memcpy(T,v,sizeof(int) * (n + 1));
repb(i,tot,1) down(i);
}
};
左偏树（Leftist Tree）
支持快速合并的堆。
结构与维护
左偏树是一棵不止权值符合堆性质且维护一个 \(\rm{dist}\) 值使得每个节点左儿子的 \(\rm{dist}\) 大于等于右节点的 \(\rm{dist}\)，即其为左偏的。
计一个左儿子或右儿子为空节点为一个外节点，其 \(\rm{dist}\) 为 \(0\)，空节点 \(\rm{dist}\) 为 \(-1\)，除此之外的节点的 \(\rm{dist}\) 为其到子树中空节点的最近距离。
由此，一个节点的 \(\rm{dist}\) 就是其右儿子 \(\rm{dist}\) 加一。
左偏树的维护关键在于合并操作。
合并
为了合并后满足堆性质，取键值较小的节点作为合并后堆的根，然后将这个根的左儿子作为合并后堆的左儿子，合并其右儿子与另一个堆，作为合并后的堆的右儿子。
在合并后检查孩子节点的 \(\rm{dist}\) 是否打破左偏性质，不符合就交换两个儿子，最后更新节点 \(\rm{dist}\) 值。
插入
把新元素作为一个堆合并进原堆即可。
查询最小值
堆顶元素即为最小值。
删除最小值
合并根的两个儿子。
减小键值
计减小键值的点为 \(u\)，如果减少键值的操作破坏了堆性质，合并这个节点的两个儿子，计合并两子节点的根为 \(v\)，将 \(u,v\) 和原来堆的根合并即可。
建树
保证元素有序的情况下，把所有元素按顺序依次加入队列中，每次从队头取出两个合并后放在队尾。
左偏树变种
斜堆是不维护 \(\rm{dist}\)，直接合并的左偏树，复杂度为 均摊的 \(\mathcal{O}(\log n)\)。
随机合并左偏树，随机数决定是否互换左右节点，期望复杂度 \(\mathcal{O}(\log n)\)。
代码
通常会配合并查集使用。
struct Node {
int val,ch[2],dist;
}T[N];
#define ls(x) (T[x].ch[0])
#define rs(x) (T[x].ch[1])
int merge(int x,int y) {
if(!x || !y) return x | y;
if(T[x].val > T[y].val)
std::swap(x,y);
rs(x) = merge(rs(x),y);
if(T[ls(x)].dist < T[rs(x)].dist)
std::swap(ls(x),rs(x));
T[x].dist = T[rs(x)].dist + 1;
return x;
}
配对堆（Pairing Heap）
合并更快，但是复杂度为均摊的多叉树结构。
结构与维护
配对堆是一棵满足堆性质的多叉树，结构性质不强。
因为子节点较多，通常不使用父亲儿子表示法，而是左孩子右兄弟表示，即每个节点只存储自己最左侧的子节点与自己右侧的一个兄弟节点。
普通的树表示方法 ：
左孩子右兄弟表示法 ：
合并
合并两个配对堆只需要把根键值较大的 \(u\) 添加作为根键值较小的 \(v\) 的左儿子，然后将 \(v\) 原来的左儿子设为 \(u\) 的右兄弟即可，计算对势能影响复杂度为均摊 \(\mathcal{O}(1)\)。
插入
把新元素作为一个堆合并进原堆即可。
查询最小值
堆顶元素即为最小值。
删除最小值
首先把根砍下来。 拿来吧你！
然后考虑如何维护剩下的节点，这个过程比较奇妙，因为根节点可以有超过两个儿子，于是需要思考一下合并儿子的过程。
首先一个 \(naive\) 的做法，按照兄弟指针依次合并，显然是 \(\mathcal{O}(n)\) 的。
然后高级一点，把所有的子节点从左往右两两分组合并，这样就是 \(\mathcal{O}(\log n)\) 的了。
这个复杂度是势能分析出来的，参见 arXiv上的这篇论文。
减小键值
首先我们维护一个父亲指针，指向其 左儿子右兄弟表示法下的 父亲，也就是左儿子父指针指向原本的父亲，其他节点父指针指向其左侧的兄弟节点。
减小节点 \(u\) 的键值时，把以 \(u\) 为根的子树提取出来（这一步需要使用父亲指针），这时候这个子树是符合堆性质的，将其与根合并即可。
这个操作的复杂度非常的玄学，下界为 \(\Omega(\log \log n)\)，上界为 \(\mathcal{O}(2^{2\sqrt{\log \log n}})\)，可以视作 \(o(\log n)\)。
代码
真的要用指针形式的话记得开内存池。
无 Decrease-Key
struct Node {
int val;
Node *ch,*sib;
Node() : val(0),ch(nullptr),sib(nullptr) {}
Node(int v) : val(v),ch(nullptr),sib(nullptr) {}
};
Node* merge(Node *x,Node *y) {
if(x == nullptr) return y;
if(y == nullptr) return x;
if(x->val > y->val)
std::swap(x,y);
y->sib = x->ch;
x->ch = y;
return x;
}
Node* MergeSon(Node *x) {
if(x == nullptr || x->sib == nullptr)
return x;
Node *y = x->sib,*z = y->sib;
x->sib = y->sib = nullptr;
return merge(merge(x,y),MergeSon(z));
}
有 Decrease-Key
struct Node {
int val;
Node *ch,*sib,*fa;
Node() : val(0),ch(nullptr),sib(nullptr),fa(nullptr) {}
Node(int v) : val(v),ch(nullptr),sib(nullptr),fa(nullptr) {}
};
Node* merge(Node *x,Node *y) {
if(x == nullptr) return y;
if(y == nullptr) return x;
if(x->val > y->val)
std::swap(x,y);
x->fa = y->fa = nullptr;
y->sib = x->ch;
if(x->ch != nullptr)
x->ch->fa = y;
x->ch = y,y->fa = x;
return x;
}
Node* MergeSon(Node *x) {
if(x == nullptr || x->sib == nullptr)
return x;
x->fa = nullptr;
Node *y = x->sib,*z = y->sib;
x->sib = y->sib = nullptr;
y->fa = nullptr;
return merge(merge(x,y),MergeSon(z));
}
Node* DecreaseKey(Node* rt,Node *x,int v) {
x->val = v;
if(x->fa == nullptr) return x;
if(x->fa->ch == x)
x->fa->ch = x->sib;
else
x->fa->sib = x->sib;
x->sib = x->fa = nullptr;
return merge(rt,x);
}
二项堆（Binomial Heap）
二项堆是以二项树为基础结构的堆。
结构与维护
二项树的结构
递归地定义二项树如下 ：
- 单个节点是一棵 \(0\) 阶二项树。
- \(r(r > 0)\) 阶二项树是由一个根节点和 \(r\) 棵子树组成的，每棵子树都是二项树且子树的阶为 \(r - 1,r - 2,\dots,1,0\)。
然后我们将这个结构用左儿子右兄弟表示出来：
发现这是一个根节点左侧接上一棵满二叉树，我们将这个结构称作 半树(Half Tree)。
阶数为 \(k\) 的二项树共有 \(2^k\) 个结点，树高为 \(k\)。深度(令根深度为 \(0\))为 \(d\) 的节点有 \(\dbinom{k}{d}\) 个。
二项堆的结构
二项堆是由许多个 阶互不相等 且点权符合堆性质的二项树组成的，所有的二项树的根节点被放在一个循环链表上，按照阶升序排列。
可以发现上面的二项树结构便于合并同阶二项树，合并两个同阶二项树时只需要把根键值较大的树作为根键值较小的树的一棵子树即可合并为阶数加一的一棵二项树。
合并
首先两个二项堆的所有二项树都是按阶升序排列的。
按照阶从小到大，在两个二项堆中如果只有一棵二项树的阶为 \(k\)，此树移动到结果堆，而如果只两棵树的阶都为 \(k\)，则合并为一个 \(k + 1\) 阶的二项树。此后这棵合并后的树将可能会和其他 \(k + 1\) 阶的二项树进行合并。
对于每个阶数 \(k\)，最多需要合并 \(3\) 棵二项树,时间复杂度为 \(\mathcal{O}(\log n)\)。
插入
把新元素作为一个堆合并进原堆即可。
查询最小值
查询二项树根链表中最小值即为最小值。
删除最小值
把根摘掉，把子树作为一个独立二项堆与原堆合并。
减小键值
类似二叉堆向上调整即可。
代码
没写，懒。
赋级配对堆（Rank Pairing Heap）
一种复杂度与斐波那契堆相同的堆，除了删除最小值为 \(\mathcal{O}(\log n)\) 之外所有操作均为\(\mathcal{O}(1)\)，为了达到更优复杂度，我们需要使用上文提到的二项堆中的二项树。
这玩意似乎还是和 Tarjan 有关系，Tarjan 发明完 Fib堆还要优化配对堆，不愧是大毒瘤。
结构与维护
我们沿着二项堆的思路走。
维护一个半树的树根链表和链表最小值指针
斐波那契堆 (Fibonacci Heap) （根本不会）
真不会，很长一段时间里也不会去学。