优先队列 | 二插堆

简介

二叉堆的逻辑结构是一颗完全二叉树,然而它的实现却是用一维数组实现的。
二叉堆分小根堆和大根堆。
对于小根堆中的结点 x,其子树的所有结点键值均大于 x,即值越小的越靠近根结点,根结点的优先级最高。(大根堆同理)
二叉堆常用于解决一些队列模拟问题,或用在其他算法中进行优化。

运行原理(手写)

对于二叉堆中的结点,假设其编号为 x,则 x 的左子树下标是 ,x 的右子树下标是 .

因此我们通过简单的计算即可访问堆中结点的子结点。

初始化

对于堆中的元素,将其初始化为优先级最低的值。比如 INF 或 -INF

插入

假设堆的大小为 ,则 进行如下的操作

  • 把 v 插入队尾, .
  • 循环比较 v 和 v 的父结点,如果 v 的优先级更高,就将他们交换;否则结束循环

由此,完成插入操作

弹出(堆顶)

假设堆的大小为 size,则 进行如下的操作

  • 把根结点赋值为优先级最小的值
  • 直接把数组末尾的元素调至堆顶的位置(不是复制), .
  • 循环比较 v 和 v 的左右子结点,将三个结点中优先级最高的与 v 交换;如果 v 本身就是最高的,结束循环

由此,完成弹出操作

代码实现

#define INF 0x3f3f3f3f
int heap[4000001],heap_size;
int n,a,x;
void heap_push(int v) {heap[++heap_size]=v;
    for(int i=heap_size; i>1; i>>=1) {if(heap[i>>1]>heap[i])heap[i>>1]^=heap[i]^=heap[i>>1]^=heap[i];
    }
}
void heap_pop() {heap[1]=heap[heap_size],heap[heap_size]=INF,heap_size--;
    int i=1;
    while(i<heap_size) {if(heap[i]<=heap[i<<1]&&heap[i]<=heap[i<<1|1])break;
        if(heap[i<<1]<heap[i<<1|1])heap[i<<1]^=heap[i]^=heap[i<<1]^=heap[i],i<<=1;
        else heap[i<<1|1]^=heap[i]^=heap[i<<1|1]^=heap[i],i=i<<1|1;}
}
int heap_top(){return heap[1];}
bool heap_empty(){return (bool)heap_size;}

STL 优先队列

  • 头文件:<queue>
  • 声明:
    template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;
  • 基本操作
    TIM20180804133129.png

重载运算符

  • 在用结构体作为优先队列的元素时,须重载 < 符号:
    struct data{
      int a,b;
      bool operator<(data tht)const{return this->a>tht.a;
      }
    };
    
  • 这里的小于是指优先级小于后者。也就是说,如果函数返回值为真,则 *this 的优先级小于 tht 的优先级,所以 tht 会比 *this 更优先出队.
  • 函数参数列表后面的 const 表示这个函数不会修改任何成员变量的值(这种 const 只对成员函数有效),是 priority_queue 重载 < 时必须有的。

对顶堆

某些题目要求维护一个有序的序列,并动态输出其中的一个值。这时为了保证序列的有序,使用一个大根堆和一个小根堆分两边维护,中间建立一个变量记录当前的答案

[POJ3784]Running Median

动态维护中位数

对顶堆模拟即可

思路就是一个大根堆一个小根堆,中间一个变量存储当前中位数。每次输入数据,调整一下两个堆的元素,输出中间的变量即可

#include<cstdio>
#include<queue>
using namespace std;
int T,s,n,ai;
priority_queue<int> p;
priority_queue<int,vector<int>,greater<int> > q;
void solve(){scanf("%d%d",&s,&n);
    printf("%d %d",s,n/2+1);
    while(!q.empty())q.pop();
    while(!p.empty())p.pop();
    int cur;
    for(int i=1;i<=n;i++){scanf("%d",&ai);
        if(i==1)cur=ai;
        else if(ai<cur)p.push(ai);
        else q.push(ai);

        if(i%2){while(p.size()>q.size())q.push(cur),cur=p.top(),p.pop();
            while(p.size()<q.size())p.push(cur),cur=q.top(),q.pop();
            if(i%20==1)puts("");
            printf("%d",cur);
        }
    }
    puts("");
}
int main(){scanf("%d",&T);
    while(T--)solve();
    return 0;
}

[LuoguP1801] 黑匣子

典型的对顶堆维护

#include<cstdio>
#include<queue>
using namespace std;
const int N=200005;
int m,n,a[N];

int mid=0x3f3f,id;
priority_queue<int,vector<int>,greater<int> >q;
priority_queue<int> p;

void add(int v){if(mid==0x3f3f)mid=v;
    else if(mid<v)q.push(v);
    else p.push(v);
}
int get(){while(p.size()<id)p.push(mid),mid=q.top(),q.pop();
    while(p.size()>id)q.push(mid),mid=p.top(),p.pop();
    ++id;
    return mid;
}
int main(){scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)scanf("%d",&a[i]);
    int cur=0;
    for(int i=1;i<=n;i++){int u;
        scanf("%d",&u);
        while(cur<u)add(a[++cur]);
        printf("%d\n",get());
    }
    return 0;
}

[POJ2442]Sequence

个长度为 的序列,每个序列各选一个数相加,可以得到 个和

求最小的 个和

分析

考虑两个序列 .

先从小到大排序

显然

因此考虑二插堆,处理完堆顶,就把堆顶之后推出的两个和入堆。

问题在于, 都可以转到 ,因此要避免重复入堆

于是我们限制入堆决策

对于

  • 时,将 入堆

  • 仅当 时,将 入堆

最后,对于 个序列,用数学归纳法,将前 个序列的前 小和作为一个序列,与第 个序列一起求两个序列的前 小和。相当于两两求前 小和即可

复杂度 .

代码

//POJ2442
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=100005;
int n,m,T,a[N],b[N],t[N];

struct data{
    int x,y;
    bool operator<(data da)const{return a[x]+b[y]>a[da.x]+b[da.y];}
};
priority_queue<data> q;
void merge(){while(!q.empty())q.pop();
    q.push((data){1,1});
    for(int i=1;i<=n;i++){data k=q.top();q.pop();
        t[i]=a[k.x]+b[k.y];
        if(k.y<n)q.push((data){k.x,k.y+1});
        if(k.x<n&&k.y==1)q.push((data){k.x+1,k.y});
    }
    for(int i=1;i<=n;i++)a[i]=t[i];
}
int main(){scanf("%d",&T);
    while(T--){scanf("%d%d",&m,&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        for(int i=1;i<m;i++){for(int j=1;j<=n;j++)scanf("%d",&b[j]);
            sort(b+1,b+n+1);
            merge();}
        for(int i=1;i<=n;i++)printf("%d",a[i]);
        puts("");
    }
    return 0;
}

[LuoguP2085] 最小函数值

个二次函数,限定定义域为正整数( ),问最小的 个函数值

分析

数学 + 二插堆

显然,开口向上,否则问题无解

于是,找到对称轴(四舍五入),从对称轴一个个加入元素即可

注意定义域

代码

#include<cstdio>
#include<queue>
using namespace std;
const int N=10004;
int n,m;
int a[N],b[N],c[N],r[N];// 四舍五入的对称轴

struct data{
    int fi,x,v;
    bool operator<(data d)const{return v>d.v;}
};
priority_queue<data> q;

int f(int fi,int pos){return a[fi]*pos*pos+b[fi]*pos+c[fi];};
int main(){scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){scanf("%d%d%d",&a[i],&b[i],&c[i]);
        double ri=b[i]/(-2.0*a[i]);// 对称轴
        r[i]=(int)ri+(ri-(int)ri<0.5?0:1);
        q.push((data){i,max(r[i],1),f(i,max(r[i],1))});
    }
    for(int i=1;i<=m;i++){data k=q.top();q.pop();
        printf("%d",k.v);
        if(k.x==r[k.fi]){q.push((data){k.fi,k.x+1,f(k.fi,k.x+1)});
            if(k.x>1)q.push((data){k.fi,k.x-1,f(k.fi,k.x-1)});
        }
        else if(k.x>r[k.fi])q.push((data){k.fi,k.x+1,f(k.fi,k.x+1)});
        else if(k.x>1)q.push((data){k.fi,k.x-1,f(k.fi,k.x-1)});
    }
    return 0;
}

[LuoguP1484] 种树

一个长度为 n 的序列,选不超过 k 个互不相邻的数,使总和最大

同 BZOJ1150

分析

双向链表 + 二插堆

如果只选一个数,显然选最大的

如果选两个数,会出现两种情况:

  • 最大和次大都选(不相邻)

  • 选最大数两边的数(如果只选一边的数,那么将这个数换成最大数可以使结果更优,故两边的数都选)

因此我们选了一个数 ,就把它前后一共三个结点合并成一个结点,标记权值为

每次我们取出堆顶,累加到答案,再合并堆顶两边的结点。这样如果之后的操作有一次累加到了 ,相当于把 抵消,总和变成 .

对于结点的合并,删除,用双向链表和二插堆同步维护即可

代码

#include<cstdio>
#include<queue>
using namespace std;
const int N=500005;
int n,m,c[N],pre[N],nex[N];
bool del[N];// 延时删除
long long ans;

struct data{
    long long v;int idx;
    bool operator<(data d)const{return v<d.v;}
};
priority_queue<data> q;

int main(){scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){scanf("%d",&c[i]);
        pre[i]=i-1,nex[i]=i+1;// 双向链表
        q.push((data){c[i],i});
    }
    for(int i=1;i<=m;i++){
        data k;
        do{k=q.top();q.pop();}while(del[k.idx]);
        if(k.v<0)break;
        ans+=k.v;
        c[k.idx]=k.v=c[pre[k.idx]]+c[nex[k.idx]]-k.v;
        // 删点
        if(pre[k.idx]!=0)del[pre[k.idx]]=1,pre[k.idx]=pre[pre[k.idx]];
        if(nex[k.idx]!=n+1)del[nex[k.idx]]=1,nex[k.idx]=nex[nex[k.idx]];
        nex[pre[k.idx]]=k.idx;
        pre[nex[k.idx]]=k.idx;
        q.push((data){k.v,k.idx});// 新结点入堆
    }
    printf("%lld",ans);
    return 0;
}

  转载请注明: Sshwy's Blog 优先队列 | 二插堆

 上一篇
最短路算法 最短路算法
摘要 复习一下模板 2019.6.4:编入精选文章 图的最短路,指的是在一个加权图 G 中某两点相距的最短路程的长度(有时要求记录路径)。 严格地说,最短路分有向与无向两种。有向的最短路强调起点和终点的区别,而无向的最短路则只需要连接两点
2018.12.05
下一篇 
[SDOI2009]HH 的项链 [SDOI2009]HH 的项链
题意静态查询区间不同的数的个数 分析对询问按右端点排序 对于每个元素,更新它最后出现的位置,然后区间求个数 树状数组维护即可 复杂度 . 代码#include<cstdio> #include<al
2018.11.29
  目录