堆

简介

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

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

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

细分表格如下：

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

二叉堆

结构

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

性质

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

由堆性质，树根存的是最值，所以可以 \(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;
}

插入

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

删除

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

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]);
}

2. 删除任意节点：此时可能会造成父节点的 \(\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);
}

可持久化堆

舍左偏树其谁？
但是可持久化数据结构先鸽了（