admin管理员组文章数量:1624320
一、定义
优先队列(Priority Queue)是一种特殊的队列,不同于常规的队列或栈数据结构。在优先队列中,每个元素都有一定的优先级,优先级最高的元素最先得到服务;优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列可以用于任何需要元素按照一定顺序处理的场景,例如操作系统任务调度、序列合并等。
二、底层实现
优先队列通常可以使用数组、链表、堆或二叉搜索树等数据结构来实现。其中,堆是最常用的底层数据结构,因为它可以在对数时间内插入和删除元素。
堆
堆是一种特殊的树形数据结构,每个节点都有一个值,通常我们所说的堆都是二叉堆。在一个最大堆中,每个节点的值都大于或等于其子节点的值;在一个最小堆中,每个节点的值都小于或等于其子节点的值。这样,最大(或最小)元素总是位于根节点。插入和删除元素需要对堆进行重新排序,但这可以在对数时间内完成。
堆分为两种主要类型:大根堆和小根堆。
-
大根堆:在大根堆中,父节点的值总是大于或等于其子节点的值。这意味着在大根堆中,根节点是最大的节点。
用大根堆实现的优先队列是从大到小:priority_queue<int> q;
-
小根堆:与大根堆相反,在小根堆中,父节点的值总是小于或等于其子节点的值。也就是说,在小根堆中,根节点是最小的节点。用小根堆实现的优先队列是从小到大:
priority_queue<int,vector<int>,greater<int> > q;
三、使用方法
在C++ 的STL中,我们可以使用priority_queue
容器来实现优先队列。下面是一些基本操作:
-
将元素x插入优先队列q中。q.push(x);
-
删除优先级最高的元素。q.pop();
-
返回优先级最高的元素。q.top();
-
如果优先队列为空,则返回true。q.empty();
四、实践
1、股票
描述
你可以预测某只股票未来N天的价格。你想从中获利,但每天你要么买一股,要么卖一股,要么什么都不做。一开始你拥有零股票,在N天结束时,你想再次拥有零股票,但想尽可能拥有更多的钱。
AC代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
priority_queue<ll,vector<ll>,greater<ll> > q;
ll n,sum;
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
ll x;
scanf("%lld",&x);
if(q.empty()||q.top()>=x){
q.push(x);
}
else{
sum+=x-q.top();
q.pop();
q.push(x);
q.push(x);
}
}
printf("%lld",sum);
return 0;
}
思路
首先,我们读入天数n和每天的股票价格x。对于每一天,我们都会检查当前的股票价格x:
如果优先队列为空,或者堆顶的元素(即最小元素)大于等于当前价格x,那么我们就将当前价格x入队。这表示我们在这一天买入了股票。否则,我们将当前价格x减去堆顶元素(即最小元素)加到总和sum中,然后将堆顶元素出队,再将当前价格x入队两次。这表示我们在这一天卖出了股票,并且立即以相同的价格买入了股票。由于题目规定每天只能进行一次交易(买入或卖出),因此这里实际上是在模拟两天的操作:第一天卖出了价格较低的股票,第二天又买入了价格较高的股票。最后,输出总和sum,即最大的利润。
2、序列合并
描述
有两个长度都是N的序列A和B,在A和B中各取一个数相加可以得到N² 个和,求这个N² 和中最小的N个。
AC代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+2;
struct node{
int x,y,sum;
friend bool operator<(node a,node b) {
return a.sum>b.sum;
}
};
priority_queue<node>q;
map<pair<ll,ll>,ll> mp;
ll a[N],b[N],sum[N];
ll n;
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;i++){
scanf("%lld",&b[i]);
}
sort(a+1,a+1+n);
sort(b+1,b+1+n);
q.push({1,1,a[1]+b[1]});
while(n--){
int x=q.top().x,y=q.top().y;
cout<<q.top().sum<<" ";
q.pop();
if(mp[{x+1,y}]==0){
q.push({x+1,y,a[x+1]+b[y]});
mp[{x+1,y}]++;
}
if(mp[{x,y+1}]==0){
q.push({x,y+1,a[x]+b[y+1]});
mp[{x,y+1}]++;
}
}
return 0;
}
思路
首先,我们定义了一个结构体node
,其中包含三个成员:x
、y
和sum
。我们重载了小于运算符,使得当一个节点的sum
值大于另一个节点的sum
值时,返回真。 然后,我们创建了一个优先队列q
,其元素类型为我们定义的结构体node
。我们还创建了一个映射mp
,用来记录已经处理过的元素对。在主函数中,我们首先读入序列A和B的长度N,并读入两个序列的元素。然后,我们对两个序列进行排序。接下来,我们将序列A和B中第一个元素的和作为一个节点插入优先队列。然后,我们进入一个循环,在每次迭代中,我们都从优先队列中取出和最小的节点,并输出其和。然后,我们检查当前节点对应的下一个元素对(即A序列中当前元素的下一个元素与B序列中当前元素的和,以及A序列中当前元素与B序列中当前元素的下一个元素的和)是否已经处理过,如果没有处理过,则将其插入优先队列,并在映射中标记为已处理。这样,当循环结束时,我们就得到了两个序列中各取一个数相加得到的N² 个和中最小的N个。
本文标签: 队列priorityqueue
版权声明:本文标题:priority_queue(优先队列)讲解 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1728894876a1178280.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论