堆

Vision271 · 2022-07-11 22:30:56 · 个人记录

概述

堆是一棵树，其中元素（点）满足如下的偏序关系：\forall now\in heap,\exists fa_{now}\to w_{fa_{now}}\leqslant /\geqslant w_{now}。
上式不等号取小于等于号的，称为小根堆；反之称为大根堆，理由显然。
我们接下来从简单堆谈起。

简单堆（二叉堆）

简单堆是一棵完全二叉树。
- 完全二叉树指的是这么一种二叉树：只有最后一层的右起连续一段可以为空。
- 另一种较为实践化的解释是，使用满二叉树的数组存储法，使用的恰好是 1\sim n 的连续段。
简单堆支持以下几个操作：
- 插入：二叉堆的插入思路比较怪，是自底向上的一种“向上调整”。具体来说，可以如下描述：
  - 记原有 n 个元素，则将插入的值放在 n+1 处，记 now=++n。
  - 不断比较 w_{now} 和 w_{fa_{now}}：
    - 如果 w_{fa_{now}}>w_{now}，则交换 w_{now} 和 w_{fa_{now}}，然后令 now=fa_{now}。
    - 否则，结束此过程。
- 删除：考虑使用一种截然相反的“向下调整”。
  - 暴力交换 w_1 和 w_n，然后记 now=1,--n。
  - 那么 w_{now} 很可能不合法。不断比较 w_{now},w_{ls_{now}},w_{rs_{now}}：
    - 如果 w_{now} 不是最小的，把三者中最小的 w_k 和 w_{now} 交换，然后 now=k。
    - 否则，结束此过程。
- 修改某个点的权值：
  - 减小：直接减小，然后向上调整。
  - 增大：直接增大，然后向下调整。
- 显然上述三个操作的复杂度都是 O(\log n)。
- 暴力合并两个堆：
  - 顾名思义，本质上就是把一者挨个插到另外一者中。
  - 不妨设 n,m 为合并的两个堆的大小，且有 n\leqslant m，下同，则复杂度为 O(n\log (n+m))。
- * 首先显然我们会 $O(n\log n)$ 的插入建堆。 * $O(n)$ 建堆的主要思路是先随便扔进去，然后自顶向下地做 $O(n)$ 次向下调整，单次复杂度为 $O(\log (n-i))$。 * 总复杂度？我不会证。 * 实际上这只是个卡常技巧，毕竟堆的操作总体而言是 $O(\log)$ 级别的，故有堆的地方的复杂度不会低于 $O(m\log n)$，其中 $m$ 为操作次数。
tips：这种任意删除/任意修改操作需要知道对应元素在堆中的位置及相应的位置关系。
- 这个关系可以靠在堆的节点上存储额外的信息来解决，但位置不行。
- 事实上，“知道它在哪个位置”正是比较主要的问题。典型代表如堆优化 dijk，有频繁的修改需求，然而要知道它在堆的哪里比较麻烦（得开额外的记录数组，并在维护堆结构的时候更新其内容）。

左偏树

左偏树是一种特殊的可并堆。顾名思义，可并堆是可以高效合并的堆。
左偏树的元素满足如下性质：
- 其中 d 以如下方式定义：d_{now}=\begin{cases} 1 & now\in leafs \\ \min_{x\in leafs}(dis(now,x)) & else\end{cases}。
- 事实上，这一定义等价于 d_{now}=\begin{cases} 1 & now\in leafs \\ d_{rs_{now}}+1 & else\end{cases}。证明显然，但需要自底向上的转移顺序。
- 我们看到，这里的 d 实际上代表着“到任意叶节点的距离”。之所以下界为 1 而非 0，主要是为了避免不在堆里的点被误认成叶子。
左偏树的核心操作，自然是维护左偏性和合并。我们下面给出基于合并的各种操作的实现（可能也有不基于合并的，但我不想想了）。
- 插入：相当于与一个单元素堆合并。实践中一般要求该函数返回新堆的根。
- 删除：相当于将以 ls_{now},rs_{now} 为根的两个堆合并。实践中一般要求该函数返回新堆的根。
- 修改权值：我暂时不会。
- 维护左偏性（push up）：
  - 首先检查是否有 d_{ls}\geqslant d_{rs}，否则交换左右儿子。注意，交换的是 now 这里指向 ls,rs 的指针。
    - 然后 d_{now}=d_{rs_{now}}+1。
- 合并：
  - 记 now_1,now_2 正在合并的两个堆（注意可能是原堆的子堆，就像线合一样）的根。开始时，now_1=rt_1,now_2=rt_2。
  - 检查是否有 w_{now_1}\leqslant w_{now_2}，否则交换 now_1,now_2。
  - 然后递归合并 rs_{now_1} 和 now_2，并将 rs_{now_1}= 返回值。
  - 维护 now_1 的左偏性，然后返回 now_1。

6.示范代码

这里使用了垃圾回收，有利于在 dsu on tree 等应用中节省空间。

namespace leftist_tree{
    struct node{
        int d,ls,rs;//这是左偏树本身的结构信息 
        ll v;
        node(){}
        node(ll _v){d=1,v=_v;}
    }a[maxn];
    int rt[maxn],tot,tsh[maxn],tstp;
    il int newnode(ll v){
        if(tstp) return a[tsh[tstp]]=node(v),tsh[tstp--];
        return a[++tot]=node(v),tot;
    }
    il void pu(int now){
        if(a[a[now].ls].d<a[a[now].rs].d) swap(a[now].ls,a[now].rs);
        a[now].d=a[a[now].rs].d+1;
        return;
    }
    il int merge(int now1,int now2){
        if(!now1 || !now2) return now1|now2;
        if(a[now1].v>a[now2].v) swap(now1,now2);
        a[now1].rs=merge(a[now1].rs,now2);
        pu(now1); return now1;
    }
    il int ins(int now1,int now2){return merge(now1,now2);}
    il int pop(int now){
        tsh[++tstp]=now;
        return merge(a[now].ls,a[now].rs);
    }
}