实现一个 std::priority_queue

简介

相较于平衡树等, 堆是一种约束较为自由的数据结构, 只需要满足父节点的键值大于/小于子节点即可.

二叉堆

下面讲解以二叉堆方式实现的大根堆, 它是一棵完全二叉树, 其保持平衡的基本方式是向上调整 (子节点与父节点交换) 与向下调整.

插入

在插入时, 将新的节点插入到完全二叉树的最后一个位置, 然后不断向上调整；

删除

在删除根节点时, 将其与最后一个节点交换, 将其删除, 然后将新的根节点不断向下调整.

建树

假设直接按照顺序构建出一棵完全二叉树, 然后对其调整使得满足堆的性质, 有两种方案:

从根开始, 不断向上调整, 这样在越深处越多节点, 走的距离期望越长, 总的复杂度期望为 $O(n\log n)$.
从叶子节点开始, 不断向下调整, 这样在越深处越多节点, 但走的距离期望短, 总的复杂度期望为 $O(n)$.

因#此, 采取第二种方案更加合理.

应用

对顶堆: 一个小根堆与一个大根堆结合, 共同维护序列的第 $k$ 大数.

左偏树

左偏树是一种可并堆. 它是一棵具有“左偏”性质的二叉树.

左偏性

dist: 一个节点到子节点中外节点的最短距离, 其中外节点指没有左儿子或没有右儿子的节点. 左偏性: 若一棵二叉树中任意节点左儿子的 dist 大于右儿子的 dist, 称其具有左偏性.

合并

合并操作是一个左偏树的核心操作, 他同时完成了合并两组数据与维持树的高度两个操作. 其核心思想是, 尽可能地往右子树里面添加东西, 如果发现添加出了问题, 就将左右子树交换. 递归地讲:

对于两个左偏树, 去值较小的根作为树根
将另一棵树与右子树合并
检查是否需要交换左右子树

其他操作

插入: 树与节点的合并
删除: 合并根的左右儿子

拓展操作

删除任意节点: 将左右儿子合并, 向上更新 dist 直到无需更新
整个堆进行算术操作: 在根上打标记, 删除/合并的时候 pushdown 即可

实现

node *merge(node *x, node *y) {
    if (x == nullptr || y == nullptr) {
        if (x == nullptr)
            x = y;
        else
            y = x;
        return x;
    }
    if (x->data > y->data)
        swap(x, y);
    x->rson = merge(x->rson, y);
    x->rson->rt = x->rt;
    if (x->lson == nullptr || x->lson->dis < x->rson->dis)
        swap(x->lson, x->rson);
    x->dis = (x->rson != nullptr) ? x->rson->dis + 1 : 0;
    return x;
}

void erase(node *x) {
    x->rt = merge(x->lson, x->rson);
    if (x->lson)
        x->lson->rt = x->rt;
    if (x->rson)
        x->rson->rt = x->rt;
    x->dis = -1;
}