题解 P3378 【【模板】堆】

Jelly_Goat · 2019-07-25 19:39:22 · 题解

今天QBXT讲基础数据结构...然后回来复习了堆...
~~上来老师就说:"我只会打左偏树"...... orz~~

好像题解区达到了49篇...
但是我还是要尝试通过通俗易懂的方式用
玄学左偏树挤进去qwq
~~想多学东西的同学不要错过~~

首先，左偏树不是严格意义上的二叉堆，而是一种堆思想延伸出的可以有堆结构的数据结构。
因为左偏树并不是完全二叉树。
那左偏树到底是个什么东西？

1.定义

首先还是要解释一个前置变量意义。

1.0 前置知识

定义：dist_i表示i到最近的第一个右子树为空的节点的距离。
还是太抽象了？那咱举个例子。
假设1右儿子是3，左儿子是2，2有左右儿子4,5，而3没有右儿子，那么dist_1=1，dist_3=0。
因为1到3的距离是1，而到其他的右儿子为空的节点的距离>1。
而且j本身就是右儿子为空的节点，所以dist_3=0，dist_1=dist_3+1=1。

上图就是这个例子的图。

1.1 定义

堆序性：满足父节点到任意子节点的链权值单调
说白了就是必须满足大根或者小根这种要求
一颗左偏树，要么子树都是左偏树，要么就是一颗空树。
左偏指的是所有的节点都满足dist_{\texttt{左儿子}}>dist_{\texttt{右儿子}}

衍生出的推论（性质）：

左偏树中任意一个节点的距离为其右儿子的距离+1。
这个很简单，因为dist_{\texttt{左儿子}}>dist_{\texttt{右儿子}}，而且dist_{father}=\min(dist_{left\_son},dist_{right\_son})，所以在左偏树中dist_{father}=dist_{right\_son}+1
证明：假设是最坏情况，那么左右必然$dist$相差为0，即是一颗完全二叉树。那么完全二叉树的$dist_{root}=log_2 n$，因此$dist_{root}$最大就只能是$log_2 n$。

2. 各种玄学操作

2.1 合并

因为左偏树节点不满足完全二叉树而且十分左偏的性质，我们可以在一个log的复杂度中合并两个堆。

这个合并分为下面几步：

1：若是其中一个堆是空的，直接return 另一个堆
2：否则选择一个堆顶val较大的堆作为父亲节点
3：(如果是val相等那么使用堆顶dist相对比较大的堆作为父亲节点)
那么现在我们将根节点的右子树和另一个堆递归合并即可
如果左右儿子dist需要修正那么交换左右儿子
更新根节点dist

就这么些。
所有的左偏树的基本操作几乎都仰仗了合并这个操作，而且也好写好理解。

2.2 插入一个新的元素

一个新的元素就是一个只有一个节点的左偏树啊！
直接合并这个左偏树和原先的左偏树即可。

2.3 弹出栈顶元素

我们可以合并根节点的左右子树，然后删除根节点（数组模拟可以加入“内存池中”）

2.4 从一个数组新建一个堆

我们参考普通二叉堆的操作，将所有元素都新建为一个一个元素的左偏树，然后全都扔到一个队列中，每次从队列中取2个堆合并，然后扔到队尾。
这样时间复杂度估计是O(n)。当然了，事情没那么简单。
有的时候出题人故意给你出一组hack数据，使得你的左偏树成了一个链，时间复杂度陡然上升......
这个时候不要心疼，直接提前O(n) random_shuffle一下再建。否则就GG了......

3. 具体应用

当然了，~~平板电视~~pd_bs库中有这个的库。
我们可以不将参数调整，默认就是左偏树。
具体可以查询C++ Conference或者OI Wiki获得更多资讯。

回到这个题上。
我们这个模板只用到了1、2、3三个操作，直接写个板子上去就好了。
但是还是不过瘾？~~来，指针预警~~
当然了，写一个指针的代码是要加注释的，所以...~~代码向预警~~

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
struct Heap //堆节点的结构体
{
    Heap *lson, *rson;//左右儿子
    int dist, val;//dist值，权值
    Heap()//构造函数：初始化
    {
        lson = rson = NULL;//左右儿子都是空的
        dist = val = 0;//dist和val自然也没有
    }
}*root = NULL;//空堆

void set_dist(Heap *node)//设置节点的dist值
{
    //如果右儿子不是空的，根据推论1，可以知道dist
    if (node->rson != NULL)
        node->dist = node->rson->dist + 1;
    //否则本身就是那个右儿子是空的节点
    else node->dist = 0;
}

Heap *merge(Heap *a, Heap *b)//合并函数，返回堆的根节点
{
    //一个节点是空的，那么返回另一个节点 
    if (a == NULL) return b;
    else if (b == NULL) return a;
    //将权值较小的作为根结点(没比较dist)
    if (a->val > b->val) swap(a, b);
    //合并右儿子和大权值节点
    a->rson = merge(a->rson, b);
    //左右儿子都不是空的
    if (a->rson != NULL && a->lson != NULL)
    {
        //比较dist并且使得左儿子dist更大
        if (a->lson->dist < a->rson->dist)
            swap(a->lson, a->rson);
    }
    //或者左儿子无，右儿子有的情况
    else if (a->lson == NULL && a->rson != NULL)
        swap(a->lson, a->rson);
    set_dist(a);//重新设置dist值
    return a;//返回根节点
}

void Insert(int val)
{
    //必须先特判堆是空的结果
    if (root == NULL)
    {
        root = new Heap();//新建节点
        root->val = val;
        set_dist(root);//设置dist值
        return ;
    }
    Heap *num = new Heap();//新建节点，作为只有一个元素的堆
    num->val = val;
    set_dist(num);//设置dist值
    root = merge(root, num);//与原先的堆合并
}

int Top()
{
    if (root != NULL)//如果不是空的
        return root->val;//返回堆顶值
    else return 0; //rand();
}

void Pop()
{
    Heap *temp = root;//将根节点先存下来
    root = merge(root->lson, root->rson);//合并左右儿子
    delete(temp);//删除原先的根节点
}

int main()
{
    int n, opt, val;
    cin >> n;//n个操作
    while (n--)
    {
        cin>>opt;//操作序号
        switch (opt)
        {
            case 1:cin>>val;Insert(val);break;//插入元素
            case 2:cout<<Top()<<endl;break;//输出堆顶元素
            case 3:Pop();break;//弹出堆顶元素
            default:break;//防止RE
        }
    }
    return 0;
}