优先队列（priority_queue）的基本概念、实现原理及常用操作。优先队列是一种根据优先级排序的数据结构，底层通常基于二叉堆实现，分为大根堆和小根堆。主要操作包括插入元素、获取队头元素、删除队头元素等。文章还通过奶牛用餐的实际案例，演示了如何利用优先队列解决任务调度问题，并提供了完整的 C++ 代码实现。
优先队列（priority queue）是一种抽象数据类型，在解决最值类题目中经常用到，而且非常简便、好用。优先队列是一种特殊的队列，其中每个元素都有一个优先级，根据这个优先级对队内的元素进行排序，根据排序的顺序分为大根堆与，正因为有这种排列顺序，在一些算法题目解答非常方便。下面进行详细介绍优先队列(priority_queue)。
假设有一个算法班级要根据算法考试成绩重新分配教室座位，7 人的算法成绩根据大根堆排列如下，那么此时学生排成的队列就属于优先队列，优先级最高的也就是分数最高的优先出队列选座位，依次进行直到队列为空为止。
我们假设新来了一位同学，他的算法成绩为 95 分，老师并不会因为他是后来的就把他放到队列最后面，而是根据他的算法成绩放到应该的位置。
优先队列是一种特殊的队列数据结构，其中每个元素都有一个与之相关的优先级，元素的出队顺序不是按照进入队列的时间（queue），而是按照优先级决定的。可以理解为每入队一个元素，此元素就去队列里面找自己的优先级位置。
特点：
前面我们说优先队列根据排序的顺序分为大根堆与小根堆，那么我们在建立优先队列时就分别可以建立两种优先队列，分别是底层基于大根堆实现的降序队列与底层基于小根堆实现的升序队列。定义优先队列需要包含头文件#include
#include<queue>//头文件 priority_queue<int> q1; q1 默认是大根堆也就是降序队列，一般写法只需要写一个类型 int、double 等 priority_queue<int,vector<int>,greater<int>> q2; q2 是小根堆也就是升序队列，三个参数必须写全，记住 greater 是升序队列 priority_queue<int,vector<int>,less<int>> q3; q3 是 q1 的具体写法，把三个参数都写上了，less 是降序队列，默认写法是 q1
优先队列的基本操作包括以下几种：
向优先队列中添加一个新元素 t，元素 t 根据优先级自动找好自己的位置。
O(log n)（基于堆的实现）。q1.push(1); int n=2; q1.push(n);
查看但不移除优先队列优先级最高/最低（大根堆/小根堆）的元素。
O(1)（基于堆的实现）。q1.push(1); int n=2; q1.push(n); q1.top();//被选取的是元素 2（大根堆）
移除并返回优先队列队头的元素。
O(log n)（基于堆的实现）。q1.push(1); int n=2; q1.push(n); q1.pop();//被删除的是元素 2（大根堆）
检查优先队列是否为空。如果为空返回 true，否则返回 false。
O(1)。while(!q1.empty()){ cout<<q1.top(); q1.pop(); }
返回优先队列中的元素数量。
O(1)。for(int i=0;i<q1.size();i++){ cout<<q1.top(); q1.pop(); }
优先队列的遍历分为两种，下面分别进行介绍，大家不必全部记住，这两种方法遍历效果是一样的，选取一种适合自己的记住以后会使用即可。
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 建立优先队列就可以，其他的一律不用，下面介绍数组、链表是为了一些笔试选择题之类，了解即可。
使用数组实现优先队列，但插入和删除操作可能需要移动其他元素，效率较低。
方式：将元素存储在数组中，每次插入时按顺序插入。出队时遍历数组找到优先级最高的元素。
O(1)。删除操作：O(n)（需要遍历找到优先级最高的元素）。使用链表实现可以避免移动元素，但查找操作效率较低。
O(n)（需要插入到正确的位置）。删除操作：O(1)。最常用的实现方式，可以快速地进行插入和删除操作。二叉堆可以是最小堆（根节点是最小元素）或最大堆（根节点是最大元素）。
O(log n)。O(log n)。删除操作：O(log n)。在编程语言中，如 C++ 的 STL、Java 的 java.util.PriorityQueue、Python 的 heapq 模块都提供了优先队列的实现。
约翰的农场有 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; }
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online