数据结构与算法：优先队列（priority_queue）

3. 删除优先级最高/低的元素（q.pop()）

移除并返回优先队列队头的元素。

• 时间复杂度：O(log n)（基于堆的实现）。

q1.push(1); int n=2; q1.push(n); q1.pop();//被删除的是元素 2（大根堆）

4. 检查是否为空（q.empty()）

检查优先队列是否为空。如果为空返回 true，否则返回 false。

• 时间复杂度：O(1)。

while(!q1.empty()){ cout<<q1.top(); q1.pop(); }

5. 获取优先队列长度（q.size()）

返回优先队列中的元素数量。

• 时间复杂度：O(1)。

for(int i=0;i<q1.size();i++){ cout<<q1.top(); q1.pop(); }

6. 优先队列的遍历

优先队列的遍历分为两种，下面分别进行介绍，大家不必全部记住，这两种方法遍历效果是一样的，选取一种适合自己的记住以后会使用即可。

a.利用 q.empty()

可以使用一个 while 循环，每次去看看优先队列是否空了，不空就输出元素，并且弹出元素；空了就结束。

while(!q1.empty()){//每次是否为空，非空就继续 cout<<q1.top()<<" ";//输出队头元素 q1.pop();//弹出队头元素 }

b.使用 for 循环

普通数组的遍历方式，注意不能使用 q1[i],因为队列没有这种形式，还是利用 q1.top() 与 q1.pop()

for(int i=0;i<q1.size();i++){//遍历到结束 q1.size(),如果知道长度为 n，可以写 n cout<<q1.top()<<" ";//输出队头元素 q1.pop();//弹出队头元素 }

四、优先队列的实现方式

优先队列有很多种实现方式，但是我们一般是利用 queue 提供的库函数来实现，直接使用 priority_queue q1 即可，其底层是利用二叉堆来实现的。我们不会利用一些什么结构体数组、链表啥的花里胡哨的东西，以后就用 priority_queue q1 建立优先队列就可以，其他的一律不用，下面介绍数组、链表是为了一些笔试选择题之类，了解即可。

1. 数组：

使用数组实现优先队列，但插入和删除操作可能需要移动其他元素，效率较低。

方式：将元素存储在数组中，每次插入时按顺序插入。出队时遍历数组找到优先级最高的元素。

• 复杂度：插入操作：O(1)。删除操作：O(n)（需要遍历找到优先级最高的元素）。
• 优点：简单易实现，适用于插入操作频繁、删除操作较少的场景。
• 缺点：删除操作效率较低。

2. 链表：

使用链表实现可以避免移动元素，但查找操作效率较低。

• 方式：将元素存储在链表中，每次插入时按优先级排序。删除操作直接从链表头部或尾部取出元素。
• 复杂度：插入操作：O(n)（需要插入到正确的位置）。删除操作：O(1)。
• 优点：删除效率较高。
• 缺点：插入效率较低，不适合频繁插入的场景。

3. 二叉堆（Binary Heap）：

最常用的实现方式，可以快速地进行插入和删除操作。二叉堆可以是最小堆（根节点是最小元素）或最大堆（根节点是最大元素）。

• 方式：二叉堆是一种完全二叉树结构，可以高效支持优先队列的操作。插入元素和删除优先级最高元素的时间复杂度均为 O(log n)。
• 复杂度：插入操作：O(log n)。删除操作：O(log n)。
• 优点：插入和删除的效率较为均衡，适合动态场景。
• 缺点：实现较为复杂，需要掌握堆的调整操作。

二叉堆的性质：

• 完全二叉树：除了最后一层外，每一层都是满的，最后一层的节点尽可能地靠左。
• 堆属性：在最小堆中，父节点的值总是小于或等于其子节点的值；在最大堆中，父节点的值总是大于或等于其子节点的值。

五、应用场景

1. 任务调度：操作系统中，优先队列可以用来调度任务，优先级高的任务先执行。
2. Dijkstra 算法：在寻找最短路径的算法中，优先队列可以用来选择下一个要处理的节点。
3. A*搜索算法：在 A*搜索算法中，优先队列可以用来选择下一个要探索的节点。
4. 事件驱动模拟：在模拟中，优先队列可以用来管理事件，确保最早发生的事件先被处理。

在编程语言中，如 C++ 的 STL、Java 的 java.util.PriorityQueue、Python 的 heapq 模块都提供了优先队列的实现。

六、算法实战

AcWing 5135. 奶牛用餐

约翰的农场有 n 头奶牛，编号 1∼n。

每天奶牛们都要去食堂用餐。

食堂一共有 k 个座位，也就是说同一时间最多可以容纳 k 头奶牛同时用餐。

已知，第 i 头奶牛到达食堂的具体时刻为 si，用餐所需花费的时间为 ti。

保证 s1<s2<…<sn。

为了让奶牛们有序用餐，约翰制定了如下规则：每头奶牛都必须由约翰安排座位用餐。每头奶牛从到达食堂的那一刻起，即刻进入待安排状态。任意时刻，只要存在空座位以及待安排奶牛，约翰就会即刻安排奶牛就座用餐。如果某一时刻，空座位的数量少于待安排奶牛的数量，则优先安排编号更小的奶牛就座用餐。每头奶牛用餐完毕的那一时刻都会被约翰立即轰走，即刻空出座位。

除了用餐花费时间以外，其它花费时间忽略不计。

请你计算并输出，每头奶牛用餐完毕的具体时刻。

输入格式

第一行包含两个整数 n,k。

接下来 n 行，其中第 i 行包含两个整数 si,ti。

注意，输入保证 s1<s2<…<sn。

输出格式

共 n 行，每行输出一个整数，其中第 i 行的整数表示第 i 头奶牛用餐完毕的具体时刻。

数据范围

前 3 个测试点满足 1≤n≤10。 所有测试点满足 1≤n,k≤5×10^5，1≤si,ti≤10^9。

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

解题思路：

本题的考点还是优先队列，哪个属性利用优先队列呢？就是每一头奶牛吃完饭的时间，我们把这个时间放在优先队列里面（小根堆），队头就是所有奶牛里面吃完饭最快的，队尾就是吃完饭最慢的。首先，我们有 k 个位置，那么前 k 头奶牛来到就可以直接进入餐厅进行吃饭，只要进了餐厅吃饭就把此奶牛的完成时间放入优先队列，这个完成时间会自动按照从小到大排序好。小根堆优先队列每次从队头弹出来是完成时间最小的一个，符合我们时间的渐进性，就是说，完成时间小的优先出来，好让外面等待的奶牛进去吃饭，例如：第一头奶牛到达时间是 1，吃饭时间是 100，第二头奶牛到达时间是 10，吃饭时间是 5，1+100>10+5，那么第二头奶牛是排在队列最前头的。前 k 头牛正在吃饭，后面如果有奶牛来，那么它只能在餐厅外面等着，因为没有空位置了。如果有一头牛吃完饭了饭，但是餐厅外面没有等候的奶牛，那么这个位置就要一直空着，直到有新的奶牛来进入餐厅吃饭。好了，废话不再多说，上代码！

代码实现：

#include<iostream> #include<queue> using namespace std; const int N=5e5+5; typedef long long ll; int n,k; pair<ll,ll> a[N];//first 表示奶牛到达食堂的时刻，，second 表示用餐所需花费的时间 priority_queue<ll,vector<ll>,greater<ll>> pq;//建立小根堆，由小到大排序 int main(){ cin>>n>>k; for(int i=0;i<n;i++){ cin>>a[i].first>>a[i].second; if(i<k){//前 k 个位置只要奶牛到达就能吃上饭 pq.push(a[i].first+a[i].second);//吃完饭花费的总时间=到达时间 + 吃饭时间 cout<<a[i].first+a[i].second<<endl; } } for(int i=k;i<n;i++){//剩余 n-k 头奶牛 if(a[i].first<=pq.top()){//如果没吃上饭的奶牛早就到达了，但是没座位，在外等候 cout<<pq.top()+a[i].second<<endl;//只要有一个奶牛出来了，等候的奶牛直接进去 pq.push(pq.top()+a[i].second); }else{//没吃上饭的奶牛还没到达，但是有空座位了 cout<<a[i].first+a[i].second<<endl;//吃完饭花费的总时间=到达时间 + 吃饭时间 pq.push(a[i].first+a[i].second); } pq.pop();//吃完了直接轰出去 } return 0; }