左偏树

左偏树(可并堆)\((Leftist Tree)\)

前置知识：

• 堆及其简单运用

前言：

• 对于很多需要堆的操作，我们都可以用\(STL\)中的\(priority\_queue\)解决。
  • 比如\(heap\_dijkstra\)，对顶堆动态维护中位数，\(Huffman\)树等....
• 但是当我们需要支持一些别的操作的时候，可能就需要我们抛弃\(STL\)，手搓这个数据结构。比如当我们遇到需要支持删除操作时，我们需要用手写堆。
• 当要求支持两个堆合并的时候，这时候我们就需要用到左偏树这个东西啦！

初识左偏树：

• 顾名思义，左偏树就是一棵向左偏的树。
• 左偏树又叫可并堆，是一种可以合并的堆，合并操作的复杂度为\(log(n_1+n_2)\)，十分的优秀。
• 接下来看一张表来对比一下普通堆和左偏树(可并堆)

堆	\(O(logn)\)	\(O(1)\)	\(O(logn)\)	\(O((n_1+n_2)log(n_1+n_2))\)
左偏树	\(O(logn)\)	\(O(1)\)	\(O(logn)\)	\(O(logn_1+logn_2)\)

• 可以结合此图加深理解：

定义：

• 左偏树是一棵二叉树，他的每个节点存储\(4\)个值，分别为左右子树，权值，距离。
  • 权值就是堆中的值。
  • 定义一个节点为外节点，当且仅当这个节点的左子树和右子树中的一个是空节点。(外节点不是叶子节点。)
  • 一个点的距离，定义为离它最近的外节点到这个节点的距离。
• 可以结合此图加深理解

(图源: 百度百科)

• 其中蓝色的数字为距离。特殊的: 规定空节点的距离为\(-1\)

性质：(基于小根堆)

• \(1:\) (堆性质) 左偏树中，父节点的权值小于等于他的孩子的权值。
  • 解释: 左偏树又叫可并堆，好歹满足一下堆性质嘛。
• \(2:\) (左偏性质)：左偏树中任意一个节点的左儿子距离一定大于等于右儿子距离。
  • 解释: 不然怎么左偏嘛。
  • 需要注意的一点，左偏指的不是左右儿子的大小。因此即使左儿子是一个点，右儿子是一个很长的链，那么也是满足要求的左偏树。
  • 同时注意，距离和深度不是一个概念，左偏树并不意味着左子树的节点数或者深度一定大于右子树。
• \(3:\) 对于左偏树的任意节点，满足他的左右子树(如果有的话)均为左偏树。
• \(4:\) 左偏树任意一个节点的距离为其右儿子的距离\(+1\)
  • 解释: 直观理解，很显然
• \(5:\) \(n\)个点的左偏树，距离最大为\(log(n+1)-1\)。(这个推论成为了左偏树时间复杂度的保证)
  • 证明: 我不会证\(QwQ\)。
    • 如果有会证的奆奆欢迎评论区或私信告诉我。

操作：(基于小根堆)

• 合并:（可并堆最基础操作，插入和删除两种操作都离不开他）
  • 合并的原理是把一颗子树
  • 当前有两个堆\(A,B\)，假设\(A\)的根节点小于\(B\)的根节点(不满足也很简单，交换\(A,B\)即可)，把\(A\)的根节点作为新的树\(C\)的根节点。
  • 之后用\(A\)的右子树和\(B\)合并。
  • 比较左右子树大小，如果右子树偏大的话，交换左右子树
  • 最后运用性质\(4\)计算一下根节点的距离
• 插入：
  • 插入就相当于只有一个节点的堆与另一个堆合并
• 删除：
  • 删除这个节点相当于将这个堆拆分成了两棵树
  • 然后将这两棵树再合并就行了

代码：

模板题

洛谷3377可并堆

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

struct LeftistTree
{
    int l, r;  //左右子树
    int fa;    //父亲节点
    int val;   //点权
    int dist;  //距离
    #define fa(x) ltree[x].fa
    #define dist(x) ltree[x].dist
    #define val(x) ltree[x].val
    #define l(x) ltree[x].l
    #define r(x) ltree[x].r
}ltree[maxn];

inline int get_fa(int x)
{
    if(fa(x) == x) return x;
    return fa(x) = get_fa(fa(x));
}

//只需要把根节点丢上来就好了
int merge_tree(int x, int y)
{
    //如果有一颗空树 直接合并
    if(!x || !y) return x + y;
    if(val(x) > val(y) || (val(x) == val(y) && x > y))
        swap(x, y);
    r(x) = merge_tree(r(x), y);
    fa(r(x)) = x;
    if(dist(l(x)) < dist(r(x)))
        swap(l(x), r(x));
    dist(x) = dist(r(x)) + 1;
    return x;
}

void pop_node(int x)
{
    int l = l(x), r = r(x);
    val(x) = -1;   //把这个点删了
    fa(l) = l; fa(r) = r;  //把原先的堆拆成两棵子树
    fa(x) = merge_tree(l, r); //将两棵树合并
}

int n, m;

int main()
{
    //小根堆的个数和操作的个数
    scanf("%d%d", &n, &m);
    //输入每一个堆的初试一个节点
    for(int i = 1, x; i <= n; i++)
    {
        scanf("%d", &x);
        fa(i) = i; val(i) = x;
    }

    for(int i = 1, op, x, y; i <= m; i++)
    {
        scanf("%d%d", &op, &x);
        if(op == 1) //将堆x和堆y合并
        {
            scanf("%d", &y);
            if(val(x) == -1 || val(y) == -1)
                continue;
            x = get_fa(x); y = get_fa(y);
            if(x != y) merge_tree(x, y);
        }
        else
        {  //输出第x个堆的堆顶 并删除堆顶
            if(val(x) == -1) puts("-1");
            else
            {
                x = get_fa(x);
                printf("%d\n", val(x));
                pop_node(x);
            }
        }
    }
    return 0;
}