堆

简介

堆是可以维护最值的数据结构。其每个节点有一个键值 \(val\) ，堆将节点按键值确定父亲/儿子关系，故把所有节点连为一棵树，通过根找到最值。

根据祖先关系可分为两类——大根堆以根节点键值最大，向叶节点递减。小根堆以根节点键值最小，向叶节点递增。

根据支持操作可分为堆、可并堆、可持久化堆，按包含顺序给出。

细分表格如下：

操作 `\` 数据结构	配对堆	二叉堆	左偏树	二项堆	斐波那契堆
插入	\(O(1)\)	\(O(\log n)\)	\(O(\log n)\)	\(O(1)\)	\(O(1)\)
查询最小值	\(O(1)\)	\(O(1)\)	\(O(1)\)	\(O(\log n)\)	\(O(1)\)
删除最小值	\(O(\log n)\)	\(O(\log n)\)	\(O(\log n)\)	\(O(\log n)\)	\(O(\log n)\)
合并	\(O(1)\)	\(O(n)\)	\(O(\log n)\)	\(O(\log n)\)	\(O(1)\)
减小一个元素的值	\(o(\log n)\)（下界 \(\Omega(\log \log n)\)，上界 \(O(2^{2\sqrt{\log \log n}}\)))	\(O(\log n)\)	\(O(\log n)\)	\(O(\log n)\)	\(O(1)\)
是否支持可持久化	\(\times\)	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)	\(\times\)

而习惯上，不加限定提到「堆」时往往都指二叉堆。

二叉堆

结构

一棵完全二叉树，每个结点中存有一个权值。

性质

父亲的权值不小于儿子的权值（大根堆）。同样的，我们可以定义小根堆。

由堆性质，树根存的是最值，所以可以 \(O(1)\) 查询。

操作

插入即放入右下角后使其上浮，删除即与右下角的节点交换后使其下沉。

实现

STL中的priority_queue已经支持了push、pop、top和通用的size、empty函数。

可并堆

左偏树

结构

一棵二叉树，每个结点定义有一个 \(\mathrm{dist}\) 值：首先定义 外节点 为左儿子或右儿子为空的节点，定义一个外节点的 \(\mathrm{dist}\) 为 \(1\)，一个不是外节点的\(\mathrm{dist}\)为其到子树中最近的外节点的距离加一。空节点的\(\mathrm{dist}\)为 \(0\)。

性质

是一种 可并堆，即具有堆的性质，并且可以快速合并，并且它是「左偏」的——每个节点左儿子的 \(\mathrm{dist}\) 都大于等于右儿子的 \(\mathrm{dist}\)。维护时使左偏树每个节点的 \(\mathrm{dist}\) 都等于其右儿子的 \(\mathrm{dist}\) 加一即可。

需要注意的是，\(\mathrm{dist}\) 不是深度，左偏树的深度没有保证，一条向左的链也是左偏树。故而实际运用时可搭配 并查集 快速查询所在堆堆顶。

操作

构建

把每个节点作为左偏树存入队列，依次取出队头两个堆合并。

合并

合并两个堆时，由于要满足堆性质，先取值较小的那个根作为合并后堆的根节点，然后将这个根的左儿子作为合并后堆的左儿子，递归地合并其右儿子与另一个堆，作为合并后的堆的右儿子。为了满足左偏性质，合并后若左儿子的 \(\mathrm{dist}\) 小于右儿子的 \(\mathrm{dist}\)，就交换两个儿子。

//用法：x = find(x), y = find(y); rt[x] = rt[y] = merge(x, y);
int merge(int x, int y) {
    if (!x || !y) return x | y;
    if (val[x] > val[y]) swap(x, y);
    rs[x] = merge(rs[x], y); fa[rs[x]] = x;
    if (dis[rs[x]] > dis[ls[x]]) swap(ls[x], rs[x]);
    dis[x] = dis[rs[x]] + 1; return x;
}

插入

将单个节点视作一棵树即可。

删除

删除根：清空根节点信息并将其左右儿子合并。

void erase(int x) {
    fa[x] = fa[ls[x]] = fa[rs[x]] = 0;
    ls[x] = rs[x] = dis[x] = rt[x] = 0; 
    rt[ls[x]] = rt[rs[x]] = merge(ls[x], rs[x]);
}

删除任意节点：此时可能会造成父节点的 \(\mathrm{dist}\) 被更新，所以我们使用pushup函数递归信息至不用更新的祖先节点即可。

void pushup(int x) {
    if (!x) return;
    if (dis[ls[x]] < dis[rs[x]]) swap(ls[x], rs[x]);
    if (dis[x] != dis[rs[x]] + 1)
        dis[x] = dis[rs[x]] + 1, pushup(fa[x]);
}
void delete(int x) {
    int fx = fa[x];
    fa[ls[x]] = fa[rs[x]] = fx;
    int rt = merge(ls[x], rs[x]);
    ls[fx] == x ? ls[fx] = rt : rs[fx] = rt;
    rt[ls[x]] = rt[rs[x]] = fx ? find(fx) : rt;
    fa[x] = ls[x] = rs[x] = dis[x] = rt[x] = 0; pushup(fx);
}

修改

需要将每个节点维护的堆与儿子合并，维护整堆修改懒标记时就要用到pushdown函数。在每次 \(merge()\) 操作和 \(erase()\) 操作时下传标记。以维护加法、乘法懒标记为例：

void pushdown(int x) {
    int m = mul[x], a = add[x]; mul[x] = 1; add[x] = 0;
    val[ls[x]] *= m; add[ls[x]] *= m; mul[ls[x]] *= m;
    val[rs[x]] *= m; add[rs[x]] *= m; mul[rs[x]] *= m;
    val[ls[x]] += a; add[ls[x]] += a; val[rs[x]] += a; add[rs[x]] += a;
}

斜堆

差别

斜堆与左偏树的唯一差别是斜堆不满足左偏性，故而斜堆的合并函数是从下往上在路径上的每个节点交换子树。

int merge(int x, int y) {
    if (!x || !y) return x | y;
    if (val[x] > val[y]) swap(x, y);
    rs[x] = merge(rs[x], y); swap(ls[x], rs[x]);
    dis[x] = dis[rs[x]] + 1; return x;
}

配对堆

结构

一棵满足堆性质的带权多叉树，且通常使用儿子 - 兄弟表示法储存一个配对堆。

struct Node {
    T v; int id;
    Node *child, *sibling;
    Node *father;//指向父/兄
};

操作

合并

套路地，令两个根节点较小的一个为新的根节点，然后将较大的根节点作为它的儿子插入进去。并且一个节点的儿子链表是按插入时间排序的，即最右边的节点最早成为父节点的儿子，最左边的节点最近成为父节点的儿子。

Node* merge(Node* x, Node* y) {
    if (x == nullptr) return y;
    if (y == nullptr) return x;
    if (x->v > y->v) swap(x, y);
    if (x->child != nullptr)
        x->child->father = y;
    y->silbing = x->child;
    y->father = x; x->child = y;
    return x;
}

插入

套路地，将新节点视作一个堆进行合并。

删除

删除根节点后要合并森林为一棵树，先拆散孩子后 从左往右 两两配对合并，再 从右往左 两两配对合并。

Node* breakup(Node* x) {
    if (x == nullptr) return nullptr;
    x->father = nullptr;
    if (x-> sibling == nullptr) return x;
    Node *y = x->sibling, *z = y->sibling;//两个兄弟
    x->sibling = y->sibling = y->father = nullptr;//拆开
    return merge(breakup(z), merge(x, y));
}
Node* erase(Node* x) {
    Node* t = breakup(x->child);
    delete x; return t;
}

修改

减小节点权值，可能需要上浮。所以我们选择将其子树拎出来重新并进去。

Node* decrease(Node *root, Node *x, T v) {
    x->v = v;
    if (x == root) return x;
    if (x->father->child == x)
        x->father->child = x->sibling;
    else x->father->sibling = x->sibling;
    if (x->sibling != nullptr)
        x->sibling->father = x->father;
    x->sibling = x->father = nullptr;
    return merge(root, x);
}