2023/6/12日学习笔记

堆

在STL中可以用优先队列来构造使用堆

std::priority_queue<int, std::vector<int> > q;//大根堆

std::priority_queue<int, std::vector<int>, std::greater<int> > q;//小根堆

push() 　          将元素插入优先队列。
pop() 　            将优先级最顶层的元素从队列中删除。（顶层不能为空）
top() 　　         输出优先队列的最顶层元素。（顶层不能为空）
size() 　　        返回优先队列的大小。
empty() 　　    验证队列是否为空。空返回1否则返回0。
swap() 　　　  将优先队列的元素与具有相同类型和大小的另一个队列交换。
emplace() 　　在优先队列的顶部插入一个新元素。

堆是一种数据结构，用来动态的维护数组中的最大或最小值

堆维护数组中的最大最小值的特性还可以扩展为维护数组中的第k大的数，k值可以发生变化，我们可以用对顶堆来维护数组中的第k大的数

对顶堆由一个大根堆和一个小根堆组成，小根堆维护比第k值大的数(大于等于k的数)，大根堆维护比第k值小的数(小于或小于等于k的数);

这两个堆构成的数据结构支持以下操作：

• 维护：当小根堆的大小小于k时，不断将大根堆堆顶元素取出并插入小根堆，直到小根堆的大小等于k；当小根堆的大小大于k时，不断将小根堆堆顶元素取出并插入大根堆，直到小根堆的大小等于k；
• 插入元素：若插入的元素大于等于小根堆堆顶元素，则将其插入小根堆，否则将其插入大根堆，然后维护对顶堆；
• 查询第 k大元素：小根堆堆顶元素即为所求；
• 删除第k大元素：删除小根堆堆顶元素，然后维护对顶堆；
• k值+1/-1:根据新的k值直接维护对顶堆。

每次插入或删除元素时调整堆的时间复杂度为Ο(logn)，如果有n个操作则时间复杂度为Ο(nlogn)

例题:

RMID2 - Running Median Again

https://www.luogu.com.cn/problem/SP16254

#Code
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;

priority_queue<int>q1;//大根堆
priority_queue<int,vector<int>,greater<int>>q2;//小根堆

//维护对顶堆的大小
void fixqu(){
    while(q1.size()<q2.size()){
        q1.push(q2.top());
        q2.pop();
    }
    while(q2.size()<q1.size()){
        q2.push(q1.top());
        q1.pop();
    }
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        while(!q1.empty())q1.pop();
        while(!q2.empty())q2.pop();
        while(1){
            int n;
            cin>>n;
            if(n==0)break;
　　　　　　　//小根堆中都是比中位数大的值,大根堆中的数都是比中位数小的数
            if(n>0){
                if(q2.size()==0)q2.push(n);
                else if(n<q2.top())q1.push(n);
                else q2.push(n);
            }
            if(n==-1){
                fixqu();
                if((q1.size()+q2.size())%2)cout<<q2.top()<<endl,q2.pop();
                else cout<<q1.top()<<endl,q1.pop();
            }
        }
    }
    return 0;
}

p1801 黑匣子

https://www.luogu.com.cn/problem/P1801

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
priority_queue<long long>q1;//大根堆
priority_queue<long long,vector<long long>,greater<long long>>q2;//小根堆
vector<long long>v;

//动态维护第k值
void fixp(int t){
    while(q1.size()>t){
        q2.push(q1.top());
        q1.pop();
    }
    while(q1.size()<t){
        q1.push(q2.top());
        q2.pop();
    }
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){int x;cin>>x;v.push_back(x);}
    int t=0;
    for(int i=0;i<m;i++){
        int x;
        cin>>x;
        while(t<x){
            if(q1.size()==0)q1.push(v[t]);
            else if(q1.top()<v[t])q2.push(v[t]);
            else q1.push(v[t]);
            t++;
        }
        fixp(i+1);
        cout<<q1.top()<<endl;
    }
}

 左偏树

左偏树是一种可合并堆，具有堆的性质，且可以用来合并堆并且求合并后的堆的最值

 dist的定义和性质:对于二叉树，定义外节点为左儿子或右儿子为空的节点，定义外节点的dist为0空节点的dist为-1,不是空节点和外节点的点的dist为该节点到最近的子树的外节点的边数

左偏树的定义和性质：

左偏树是一颗二叉树，左偏树具有堆的性质并且还具有左偏的性质：每个节点的左儿子的dist都大于等于右儿子的dist，因此左偏树的每个节点的dist都等于其右儿子的dist加1

左偏树的核心操作：合并操作

因为左偏树也具有堆的性质，所以左偏树也分小根堆和大根堆，以小根堆为例，在合并两个堆的时候，首先先要判断这两个堆是否非空，若其中一个堆为空则返回非空的那一个堆，然后在比较这两个堆的根节点的值的大小，选择值小的作为新堆的根节点，然后将这个根的左儿子作为合并后新堆的左儿子，递归的合并其右儿子与另一个堆，作为合并后的右儿子，若合并后的左儿子的dist小于右儿子的dist，则交换两个儿子。

int merge(int x,int y){
    if(!x||!y)return x||y;//判断是否非空
    if(x>y)swap(x,y);
    rc[x]=merge(rc[x],y);//递归合并根的右节点和另一个堆
    if(dist[lc[x]]<dist[rc[x]])swap(rc[x],lc[x]);
    dist[x]=dist[rc[x]]+1;
    return x;
}

左偏树的其他基本操作

插入给定值：插入值相当于是将该节点与左偏树合并

求最小/大值：小根堆或大根堆的根节点即为其所要求的最值

删除最小值/最大值：即删除根节点，只要合并根节点的左右儿子即可，记得维护已删除节点的信息。

给定一个节点，求其所在左偏树的根节点:我们可以利用并查集的方法，记录每个节点的父亲节点，然后递归寻找根节点

//路径压缩方式递归
int find(int x){
    return pre[x]==x?x:pre[x]=find(pre[x]);
}

使用路径压缩的方式递归求左偏树的根节点时，需要维护pre[x]的值，在合并两个节点时x,y时，pre[x]=pre[y]=merge(rc[x],y);

在删除左偏树中的最小值时，令pre[rc[x]]=pre[lc[x]]=pre[x]=merge(lc[x],rc[x]);因为x是之前的根节点，在路径压缩时可能有pre的值指向x，所以也要更新x的值，使其指向合并后的新的根节点。

由于x已经被作为中间量使用得不成样子，如果之后还要用到结点x，需要新建一个值相同的结点。

例题:p377 左偏树模板

https://www.luogu.com.cn/problem/P3377

#include<iostream>
#include<algorithm>
using namespace std;
const int maxm = 100005;

int rc[maxm],lc[maxm],dist[maxm],pre[maxm];
struct node{
    int id,v;
    bool operator<(node x)const{return v==x.v?id<x.id:v<x.v;}//重定义，重新定义小于号，按照v值大小升序，当v值相同时，id值升序
}t[maxm];

bool tf[maxm];

int find(int x){
    return pre[x]==x?x:pre[x]=find(pre[x]);
}

int merge(int x,int y){
    if(!x||!y)return x+y;
    if(t[y]<t[x])swap(x,y);
    rc[x]=merge(rc[x],y);
    if(dist[lc[x]]<dist[rc[x]])swap(lc[x],rc[x]);
    dist[x]=dist[rc[x]]+1;
    return x;
}

void add(){
    int x,y;
    cin>>x>>y;
    if(tf[x]||tf[y])return;
    int X=find(x),Y=find(y);
    if(X!=Y)pre[X]=pre[Y]=merge(X,Y);
}

void del(){
    int x;
    cin>>x;
    if(tf[x]){
        cout<<-1<<endl;
        return;
    }
    int X=find(x);
    cout<<t[X].v<<endl;
    tf[X]=true;
    pre[lc[X]]=pre[rc[X]]=pre[X]=merge(lc[X],rc[X]);
    lc[X]=rc[X]=dist[X]=0;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    dist[0]=-1;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        rt[i]=i;
        cin>>t[i].v;
        t[i].id=i;
    }
    for(int i=0;i<m;i++){
        int x;
        cin>>x;
        switch (x){
            case 1:add();break;
            case 2:del();break;
        }
    }
    return 0;
}