STL课程第七课《国王的排行榜——认识 Priority Queue优先队列》本课目标理解什么是 Priority Queue优先队列。知道 Priority Queue 与 Queue 的区别。熟练掌握push()、pop()、top()、size()、empty()。掌握默认最大堆最大值优先。掌握最小堆最小值优先的写法。能解决排行榜、找最大值、找最小值等问题。为以后学习堆排序、贪心算法、Dijkstra算法打基础。第一幕 国王举办武林大会程序王国举行武林大会。来了很多高手。他们的武功分别是小明 80 小红 95 小刚 70 小美 100 小军 88请问如果他们排普通队伍。是不是先来的先比赛同学们回答是的。可是今天国王宣布武功最高的人先上场无论谁先来。只看武功高低。我们画图普通队列Queue 小明 → 小红 → 小刚 → 小美 优先队列Priority Queue 小美100 小红95 小军88 小明80 小刚70今天需要认识一个新朋友。叫Priority Queue中文名字优先队列意思就是谁更重要谁先出来。第二幕 Queue和Priority Queue有什么不同画表QueuePriority Queue谁先来谁先走谁最大谁先走FIFO按优先级排队排行榜总结普通队列。按时间。优先队列。按大小。第三幕 请出Priority Queue首先。头文件#includeiostream #includequeue using namespace std;创建priority_queueint pq;解释。priority优先。queue队列。pq。变量名字。第四幕 放入数字依次加入pq.push(50); pq.push(90); pq.push(30); pq.push(100); pq.push(80);请问现在。谁站最前面同学们猜是不是100答案正确✅️。因为Priority Queue。永远把最大的放前面。第五幕 看看第一名程序coutpq.top();输出100不是第一个加入。而是最大的。第六幕 第一名离开执行pq.pop();100离开。请问。新的第一名是谁答案90。再pop();变成80。画图开始100 90 80 50 30↓pop90 80 50 30↓pop80 50 30是不是很像排行榜。第七幕 演示程序#includeiostream #includequeue using namespace std; int main() { priority_queueint pq; pq.push(50); pq.push(90); pq.push(30); pq.push(100); pq.push(80); while(!pq.empty()) { coutpq.top() ; pq.pop(); } return 0; }输出100 90 80 50 30请看输出时。已经自动排好了。第八幕 如果我要最小的怎么办如果医院今天要先看年龄最小的人。怎么办默认。Priority Queue。最大的在前。现在。我们想最小的在前。怎么办我们请出一个新魔法greaterint创建priority_queueint, vectorint, greaterint pq;看起来很长。可以直接套模板。第九幕 最小堆程序priority_queueint, vectorint, greaterint pq; pq.push(50); pq.push(90); pq.push(30); pq.push(100); pq.push(80);输出30 50 80 90 100最大的。变成最小的。第十幕 最大堆和最小堆最大堆100 90 80 50 30最小堆30 50 80 90 100口诀默认最大。greater就是最小。第十一幕 课堂实践一——成绩排行榜输入90 75 100 88 95要求输出100 95 90 88 75参考程序priority_queueint pq; int n; cinn; for(int i0;in;i) { int x; cinx; pq.push(x); } while(!pq.empty()) { coutpq.top() ; pq.pop(); }第十二幕 课堂实践二——找最小数字输入8 12 5 30 1 18要求输出1 5 12 18 30同学们来完成最小堆。第十三幕 Priority Queue和Sort有什么区别画表SortPriority Queue一次排好随时加入全部排序每次只关心第一名排完不变可以不断加入新数据举例学校成绩。考完一次。排序。用sort。直播间人气。一直变化。用Priority Queue。第十四幕 Priority Queue能保存结构体吗当然可以。还可以使用cmp。堆。后面会讲。今天大家先认识。整数版本。第十五幕 真正的大本领Priority Queue。以后。会出现在 Top K 最大值 Top K 最小值 堆排序 Dijkstra最短路 Huffman哈夫曼树 贪心算法几乎每次。NOIP。CSP。都会见到。本课总结今天我们认识了Priority Queue优先队列。它最大的特点就是不是谁先来谁先走而是谁的优先级高谁先出来。掌握了五个常用成员函数成员函数作用生活中的理解push(x)加入元素新选手进入排行榜pop()删除优先级最高的元素第一名离场top()查看当前第一名看冠军是谁size()元素个数排行榜人数empty()是否为空排行榜是否为空默认排序规则写法排序结果priority_queueint最大值优先最大堆priority_queueint, vectorint, greaterint最小值优先最小堆同学们只要记住一句口诀默认最大greater最小。Queue、Stack、Priority Queue 三兄弟对比容器中文名称谁先出来生活中的例子queue队列先来的先出来FIFO排队买票、排队打饭stack栈后来的先出来LIFO叠盘子、撤销操作priority_queue优先队列最大的或最小的先出来成绩排行榜、比赛排名、急诊分诊画一张总结图Queue排队 ① → ② → ③ → ④ 出来 ①②③④ Stack盘子 ④ ③ ② ① 出来 ④③②① Priority Queue排行榜 100 95 88 80 70 出来 1009588……这里表示按优先级依次取出。今天同学们知道了sort是给所有人排队priority_queue更像是随时维护排行榜。这样以后学习 Top K、堆、贪心算法时我们会可以考虑使用优先队列。
