c++优先队列(堆)
2024-10-18 17:16:06
1.最小堆、最大堆
priority_queue<int,vector<int>,greater<int> > f; //最小堆(后面的数逐渐greater)
priority_queue<int,vector<int>,less<int> > f;//最大堆(后面的数逐渐less)
(1).合并果子
https://www.vijos.org/p/1097
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <stdbool.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std; priority_queue<int,vector<int>,greater<int> > f; int main()
{
long n,i,a,x,y=;
scanf("%ld",&n);
for (i=;i<=n;i++)
{
scanf("%ld",&a);
f.push(a);
}
for (i=;i<n;i++)
{
x=f.top();
f.pop();
x+=f.top();
f.pop();
f.push(x);
y+=x;
}
printf("%ld",y);
return ;
}
2.自定义
测试：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <stdbool.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;
#define maxn 100000+5
#define inf 100000+5 long f[maxn],pos[maxn]; //×î´ó¶Ñ
struct cmp1
{
bool operator() (long a,long b)
{
return f[a]<f[b];
}
}; //×îС¶Ñ
struct cmp2
{
bool operator() (long a,long b)
{
return f[a]>f[b];
}
}; //Ç°1/2:a ºó1/2£ºb
priority_queue<int,vector<int>,cmp1 > a;
priority_queue<int,vector<int>,cmp2 > b; int main()
{
long n,d,i;
scanf("%ld",&n);
for (i=;i<=n;i++)
{
scanf("%ld",&f[i]);
// a.push(i);
b.push(i);
}
// while (!a.empty())
while (!b.empty())
{
// printf("%ld ",f[a.top()]);
// a.pop();
printf("%ld ",f[b.top()]);
b.pop();
}
return ;
}
/*
5
2 4 5 1 3
*/
最短路用堆实现，时间复杂度O(nlogn)，其实可以用下面的3方法实现，使堆中的数据永远小于等于n个，但是编写比较复杂
两道例题：
http://www.cnblogs.com/cmyg/p/8727643.html
3.对于需要修改、删除堆里的数据，需要自行写堆(优先队列) 参见算法导论
以下是使用优先队列修改、删除堆里的数据，发生错误的案例(代入数据)：
//要删除指定值的话只能自己写一个优先队列
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <stdbool.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;
#define maxn 100000+5
#define inf 100000+5 long f[maxn],pos[maxn]; //最大堆
struct cmp1
{
bool operator() (long a,long b)
{
return f[a]<f[b];
}
}; //最小堆
struct cmp2
{
bool operator() (long a,long b)
{
return f[a]>f[b];
}
}; //从小到大排序
//前(n+1)/2个数：a(最大堆)
//后n/2个数：b(最小堆)
//中位数永远是a的最大值
//增添和删除：也许需要a的最大值移向b或b的最小值移向a
priority_queue<int,vector<int>,cmp1 > a;
priority_queue<int,vector<int>,cmp2 > b; void change()
{
long d;
if (a.size()<b.size())
{
d=b.top();
b.pop();
a.push(d);
pos[d]=;
}
else if (a.size()>b.size()+)
{
d=a.top();
a.pop();
b.push(d);
pos[d]=;
}
} int main()
{
long n,g;
char s[];
scanf("%ld",&n);
while (n)
{
n--;
scanf("%s",s);
if (strcmp(s,"Pop")==)
{
if (g==)
{
printf("Invalid\n");
continue;
}
printf("%ld\n",f[g]);
if (pos[g]==)
{
f[g]+=inf; printf("--%ld\n",a.top()); a.pop(); printf("--%ld\n",a.top());
//这里错了
}
else
{
f[g]-=inf;
b.pop();
}
g--;
change();
}
else if (strcmp(s,"Push")==)
{
g++;
scanf("%ld",&f[g]);
if (a.empty() || f[g]<=f[a.top()])
{
a.push(g);
pos[g]=;
}
else
{
b.push(g);
pos[g]=;
}
change();
}
else
{
if (g==)
printf("Invalid\n");
else
printf("%ld\n",f[a.top()]);
}
}
return ;
}
/*
100
Push 1
PeekMedian
Push 2
PeekMedian
Push 3
PeekMedian
Push 4
PeekMedian
Push 5
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop 100
Push 5
PeekMedian
Push 4
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop */
3.1 求第k大，k的值每次最多变化为1
求中位数
https://www.patest.cn/contests/gplt/L3-002
Solution：
分成两个堆，
对数从小到大排序
前(n+1)/2个数：a(最大堆)
后n/2个数：b(最小堆)
中位数永远是a的最大值
增添和删除：也许需要a的最大值移向b或b的最小值移向a
注意pos和input数组，这个是用于定位的，从而可以修改数据，删除数据
//还可以求第k大(k值固定) //要删除指定值的话只能自己写一个优先队列
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <stdbool.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;
#define maxn 100000+5
#define inf 100000+5 struct node
{
long d,g;
}; long f[maxn],treenum[maxn];
//posa[i],posb[i]:a/b中第i个点在输入中的位置
//input[i]:输入中第i个点在树的位置(pos标记是在哪棵树)
long a[maxn],b[maxn],posa[maxn],posb[maxn],input[maxn]; //最大堆
struct cmp1
{
bool operator() (long a,long b)
{
return f[a]<f[b];
}
}; //最小堆
struct cmp2
{
bool operator() (long a,long b)
{
return f[a]>f[b];
}
}; //从小到大排序
//前(n+1)/2个数：a(最大堆)
//后n/2个数：b(最小堆)
//中位数永远是a的最大值
//增添和删除：也许需要a的最大值移向b或b的最小值移向a
//priority_queue<int,vector<int>,cmp1 > a;
//priority_queue<int,vector<int>,cmp2 > b; void up_min(long t[],long pos[],long input[],long i)
{
long j,temp;
while (i>)
{
j=i>>;
//j<i
if (t[j]>t[i])
{
temp=t[i];
t[i]=t[j];
t[j]=temp; temp=pos[i];
pos[i]=pos[j];
pos[j]=temp; input[pos[i]]=i;
input[pos[j]]=j;
}
else
break;
i=j;
}
} void down_min(long t[],long pos[],long input[],long i)
{
long j,temp;
while (( i<<)<=t[])
{
j=i<<;
if (j!=t[] && t[j+]<t[j])
j=j|;
//i<j
if (t[i]>t[j])
{
temp=t[i];
t[i]=t[j];
t[j]=temp; temp=pos[i];
pos[i]=pos[j];
pos[j]=temp; input[pos[i]]=i;
input[pos[j]]=j;
}
else
break;
i=j;
}
} void push_min(long t[],long pos[],long input[],struct node p)
{
t[]++;
t[t[]]=p.d;
pos[t[]]=p.g;
input[p.g]=t[];
up_min(t,pos,input,t[]);
} void pop_min(long t[],long pos[],long input[])
{
t[]=t[t[]];
pos[]=pos[t[]];
input[pos[]]=;
t[]--;
down_min(t,pos,input,);
} void minus_min(long t[],long pos[],long input[],long w,long d)
{
t[w]-=d;
up_min(t,pos,input,w);
} void plus_min(long t[],long pos[],long input[],long w,long d)
{
t[w]+=d;
down_min(t,pos,input,w);
} void up_max(long t[],long pos[],long input[],long i)
{
long j,temp;
while (i>)
{
j=i>>;
//j<i
if (t[j]<t[i])
{
temp=t[i];
t[i]=t[j];
t[j]=temp; temp=pos[i];
pos[i]=pos[j];
pos[j]=temp; input[pos[i]]=i;
input[pos[j]]=j;
}
else
break;
i=j;
}
} void down_max(long t[],long pos[],long input[],long i)
{
long j,temp;
while ((i<<)<=t[])
{
j=i<<;
if (j!=t[] && t[j+]>t[j])
j=j|;
//i<j
if (t[i]<t[j])
{
temp=t[i];
t[i]=t[j];
t[j]=temp; temp=pos[i];
pos[i]=pos[j];
pos[j]=temp; input[pos[i]]=i;
input[pos[j]]=j;
}
else
break;
i=j;
}
} void push_max(long t[],long pos[],long input[],struct node p)
{
long i,j,temp;
t[]++;
t[t[]]=p.d;
pos[t[]]=p.g;
input[p.g]=t[];
up_max(t,pos,input,t[]);
} void pop_max(long t[],long pos[],long input[])
{
t[]=t[t[]];
pos[]=pos[t[]];
input[pos[]]=;
t[]--;
down_max(t,pos,input,);
} void plus_max(long t[],long pos[],long input[],long w,long d)
{
t[w]+=d;
up_max(t,pos,input,w);
} void minus_max(long t[],long pos[],long input[],long w,long d)
{
t[w]-=d;
down_max(t,pos,input,w);
} long size(long t[])
{
return t[];
} struct node top(long t[],long pos[])
{
struct node p;
p.d=t[];
p.g=pos[];
return p;
} bool empty(long t[])
{
if (t[]==)
return true;
else
return false;
} void change()
{
struct node cond;
long d;
if (size(a)<size(b))
// if (a.size()<b.size())
{
cond=top(b,posb);
pop_min(b,posb,input);
push_max(a,posa,input,cond);
// d=b.top();
// b.pop();
// a.push(d);
treenum[cond.g]=;
}
else if (size(a)>size(b)+)
// else if (a.size()>b.size()+1)
{
cond=top(a,posa);
pop_max(a,posa,input);
push_min(b,posb,input,cond);
// d=a.top();
// a.pop();
// b.push(d);
treenum[cond.g]=;
}
} int main()
{
struct node cond;
long n,g;
char s[];
a[]=; b[]=;
scanf("%ld",&n);
while (n)
{
n--;
scanf("%s",s);
if (strcmp(s,"Pop")==)
{
if (g==)
{
printf("Invalid\n");
continue;
}
printf("%ld\n",f[g]);
if (treenum[g]==)
{
// f[g]+=inf;
// a.pop();
plus_max(a,posa,input,input[g],inf);
pop_max(a,posa,input);
}
else
{
// f[g]-=inf;
// b.pop();
minus_min(b,posb,input,input[g],inf);
pop_min(b,posb,input);
}
g--;
change();
}
else if (strcmp(s,"Push")==)
{
g++;
scanf("%ld",&f[g]);
// if (a.empty() || f[g]<=f[a.top()])
if (empty(a) || f[g]<=top(a,posa).d)
{
cond.d=f[g];
cond.g=g;
// a.push(g);
push_max(a,posa,input,cond);
treenum[g]=;
}
else
{
cond.d=f[g];
cond.g=g;
// b.push(g);
push_min(b,posb,input,cond);
treenum[g]=;
}
change();
}
else
{
if (g==)
printf("Invalid\n");
else
// printf("%ld\n",f[a.top()]);
printf("%ld\n",top(a,posa).d);
}
}
return ;
}
/*
100
Push 1
PeekMedian
Push 2
PeekMedian
Push 3
PeekMedian
Push 4
PeekMedian
Push 5
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop 100
Push 5
PeekMedian
Push 4
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop
PeekMedian
Pop */
3.2 求第k大的数(k永远不变)
前k大的数放入最小堆a，其它的数放入最大堆b
添加数据：数据放入堆a，若堆a的大小大于k，则取最小的数放入堆b
修改数据：修改后根据情况是否把一个数从a移至b或从b移至a
最新文章
- C# 异步操作 async await
- iis
- 来抢你们IT狗的饭碗了
- android产品业务逻辑对app稳定影响太大
- Java代码操作Redis的sentinel和Redis的集群Cluster操作
- 常见dos命令
- JVM 堆和栈的区别
- 利用qq设置个性化的域名邮箱
- 关于前端本地压缩图片，兼容IOS/Android/PC且自动按需加载文件之lrz.bundle.js
- HTTP属性管理器 初探
- rabbitmq 配置集群镜像
- 聊聊ReentrantLock的内部实现
- Linux基础命令---ping
- 转Genymetion
- C# MemoryStream BinaryReader
- 【scala】scala 数组 (三)
- Android图片加载框架最全解析（一），Glide的基本用法
- vs2010 javascript代码拓展插件支持代码折叠
- Visual Studio2010 支持MVC4开发
- Canvas学习：globalCompositeOperation详解