C语言中如何实现一个支持长尾词插入和删除操作的优先队列？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1319个文字，预计阅读时间需要6分钟。
C++中的优先队列（Priority Queue）是一种特殊的队列，其中的元素根据特定的优先级进行排序。元素按照一定的优先级级序排列，每次取出的是优先级最高的元素。优先队列的特点是每次取出元素都是优先级最高的，即优先级最高的元素总是位于队列的头部。在C++中，优先队列通常通过`queue`容器实现。
C++中的优先队列（Priority Queue）是一种特殊的队列，其中的元素按照一定的优先级进行排序。优先队列的特点是每次取出的元素都是优先级最高的元素。
在C++中，优先队列是通过<queue>头文件中的priority_queue模板类来实现的。下面是一个简单的示例，演示了如何使用优先队列：
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
// 插入元素
pq.push(30);
pq.push(10);
pq.push(50);
pq.push(20);
// 访问队列中的元素
std::cout << "队列中的元素: ";
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
std::cout << std::endl;
return 0;
}
在上述示例中，我们首先创建了一个整数类型的优先队列 pq。然后，我们使用push()函数向队列中插入元素。注意，插入的元素会根据默认的比较函数（通常是大顶堆）进行排序。
接下来，我们使用top()函数访问队列中的元素，该函数返回队列中优先级最高的元素。然后，我们使用pop()函数将队列中的元素移除，以便访问下一个优先级最高的元素。我们可以使用empty()函数检查队列是否为空。
最后，我们输出队列中的元素，可以看到它们按照优先级从高到低的顺序进行了排序。
需要注意的是，优先队列默认使用<运算符进行元素的比较，因此对于自定义类型的元素，需要重载<运算符或提供自定义的比较函数来定义元素的优先级。
优先队列在许多算法和数据结构中都有广泛的应用，例如Dijkstra算法、堆排序等。它提供了一种方便的方式来处理具有优先级的元素。
优先队列的出队顺序默认按元素值从大到小进行
例题
1、加油站
分析：因为只需要得到加几次油，并不用找到在哪个加油站加油。当油量不够时，优先在油量大的加油站加油。
#include<bits/stdc++.h>
using namespace std;
const int maxN=10005;
int A[maxN],B[maxN];
int N,L,P;
void solve()
{
A[N]=L;
B[N]=0;//为了方便将终点也视为一个加油站
N++;
priority_queue<int>que;
int ans=0,pos=0,tank=P;//加油次数、现在的位置、油箱中的汽油量
for(int i=0;i<N;i++)
{
int d=A[i]-pos;
while(tank<d)//油箱中的油不够时
{
if(que.empty())
{
printf("-1\n");//没油可加
return;
}
tank+=que.top();//加上最大的油
que.pop();
ans++;
}
tank-=d;
pos=A[i];//更新所在位置
que.push(B[i]);//将该加油站的油入队
}
printf("%d\n",ans);
}
int main()
{
while(scanf("%d%d%d",&N,&L,&P)&&N)
{
for(int i=0;i<N;i++)
{
scanf("%d",&A[i]);
}
for(int i=0;i<N;i++)
{
scanf("%d",&B[i]);
}
solve();
}
return 0;
}
2、修栅栏
分析：每次只需要选取长度较小的两块板
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
//声明一个从小到大取出数值的优先队列
priority_queue<int,vector<int>,greater<int>>que;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int num;
scanf("%d",&num);
que.push(num);
}
long long ans=0;
//直到队列中只剩下一个元素
while(que.size()>1)
{
int l1=que.top();
que.pop();
int l2=que.top();
que.pop();
ans+=(l1+l2);
que.push(l1+l2);
}
printf("%lld",ans);
return 0;
}
本文共计1319个文字，预计阅读时间需要6分钟。
C++中的优先队列（Priority Queue）是一种特殊的队列，其中的元素根据特定的优先级进行排序。元素按照一定的优先级级序排列，每次取出的是优先级最高的元素。优先队列的特点是每次取出元素都是优先级最高的，即优先级最高的元素总是位于队列的头部。在C++中，优先队列通常通过`queue`容器实现。
C++中的优先队列（Priority Queue）是一种特殊的队列，其中的元素按照一定的优先级进行排序。优先队列的特点是每次取出的元素都是优先级最高的元素。
在C++中，优先队列是通过<queue>头文件中的priority_queue模板类来实现的。下面是一个简单的示例，演示了如何使用优先队列：
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
// 插入元素
pq.push(30);
pq.push(10);
pq.push(50);
pq.push(20);
// 访问队列中的元素
std::cout << "队列中的元素: ";
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
std::cout << std::endl;
return 0;
}
在上述示例中，我们首先创建了一个整数类型的优先队列 pq。然后，我们使用push()函数向队列中插入元素。注意，插入的元素会根据默认的比较函数（通常是大顶堆）进行排序。
接下来，我们使用top()函数访问队列中的元素，该函数返回队列中优先级最高的元素。然后，我们使用pop()函数将队列中的元素移除，以便访问下一个优先级最高的元素。我们可以使用empty()函数检查队列是否为空。
最后，我们输出队列中的元素，可以看到它们按照优先级从高到低的顺序进行了排序。
需要注意的是，优先队列默认使用<运算符进行元素的比较，因此对于自定义类型的元素，需要重载<运算符或提供自定义的比较函数来定义元素的优先级。
优先队列在许多算法和数据结构中都有广泛的应用，例如Dijkstra算法、堆排序等。它提供了一种方便的方式来处理具有优先级的元素。
优先队列的出队顺序默认按元素值从大到小进行
例题
1、加油站
分析：因为只需要得到加几次油，并不用找到在哪个加油站加油。当油量不够时，优先在油量大的加油站加油。
#include<bits/stdc++.h>
using namespace std;
const int maxN=10005;
int A[maxN],B[maxN];
int N,L,P;
void solve()
{
A[N]=L;
B[N]=0;//为了方便将终点也视为一个加油站
N++;
priority_queue<int>que;
int ans=0,pos=0,tank=P;//加油次数、现在的位置、油箱中的汽油量
for(int i=0;i<N;i++)
{
int d=A[i]-pos;
while(tank<d)//油箱中的油不够时
{
if(que.empty())
{
printf("-1\n");//没油可加
return;
}
tank+=que.top();//加上最大的油
que.pop();
ans++;
}
tank-=d;
pos=A[i];//更新所在位置
que.push(B[i]);//将该加油站的油入队
}
printf("%d\n",ans);
}
int main()
{
while(scanf("%d%d%d",&N,&L,&P)&&N)
{
for(int i=0;i<N;i++)
{
scanf("%d",&A[i]);
}
for(int i=0;i<N;i++)
{
scanf("%d",&B[i]);
}
solve();
}
return 0;
}
2、修栅栏
分析：每次只需要选取长度较小的两块板
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
//声明一个从小到大取出数值的优先队列
priority_queue<int,vector<int>,greater<int>>que;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int num;
scanf("%d",&num);
que.push(num);
}
long long ans=0;
//直到队列中只剩下一个元素
while(que.size()>1)
{
int l1=que.top();
que.pop();
int l2=que.top();
que.pop();
ans+=(l1+l2);
que.push(l1+l2);
}
printf("%lld",ans);
return 0;
}