实现一个 std::priority_queue

简介

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

二叉堆

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

插入

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

删除

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

建树

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

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

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

应用

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

左偏树

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

左偏性

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

合并

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

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

其他操作

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

拓展操作

  1. 删除任意节点:将左右儿子合并,向上更新 dist 直到无需更新
  2. 整个堆进行算术操作:在根上打标记,删除/合并的时候 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;
}



Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • OI 退役日记 (fake)
  • 「题解 P2282」HNOI2003 历史年份
  • 基于 antlr4 的 Python 解释器
  • 「题解 P5072」Ynoi2015 盼君勿忘
  • 「题解 P6830」IOI2020 连接擎天树