学会了吗queue(queue什么意思)

在刷题过程中，我们会遇到求第K大元素这样的问题，其中一种效率还可以的做法是使用优先级队列实现，底层数据结构一

在刷题过程中，我们会遇到求第K大元素这样的问题，其中一种效率还可以的做法是使用优先级队列实现，底层数据结构一般是堆我估计很多同学搞不清楚优先级队列和堆的区别，不服的举手，这个问题我们最后讨论，我们先来仔细看看C++标准库中priority_queue的用法，这是本文的重点。

优先级队列操作priority_queue这个类在STL的queue文件中，有如下方法：

首先是top函数，这个函数返回堆顶的元素，大堆返回最大的元素，小堆返回最小的元素其次是大小接口，empty函数是检查容器是否为空，size返回元素的个数然后最重要的是修改操作，push函数可以插入元素到队列中，emplace函数也是插入，这2个有啥区别呢？注意C++11的容器操作很多都加了emplace相关的函数，这个函数更加高效，可以减少拷贝，一般情况下优先使用emplace函数，性能和内存都会好些。

修改操作pop就是将堆顶元素删除掉swap是干什么的？swap操作有点特别，如下例子：// priority_queue::swap#include       // std::cout。

#include          // std::priority_queueintmain(){std::priority_queue foo,bar;  foo.push (

15); foo.push(30); foo.push(10);  bar.push (101); bar.push(202);  foo.swap(bar);std::cout << "size of foo: "

 << foo.size() << \n;std::cout << "size of bar: " << bar.size() << \n;return0;}这个例子会输出：size of foo: 2

size of bar: 3也即是说，swap是交换两个容器的数据，这种操作一般可以在外部自己实现，标准库提供了这个接口看了是考虑性能构造函数 - 比较参数优先级队列的功能就这些，下面我们来看看构造函数：。

auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };std::priority_queue

vector, decltype(cmp)> q3(cmp);模板有3个参数，第一个参数是类型，第二个参数是底层放数据的容器类型，第三个参数是比较函数，上面是将cmp这个参数传进去作为比较函数。

基本上就这些内容，如何实现求第K大的树呢？我们只需要让这个队列一直保留K个元素，堆顶的元素就是第K大的区别下面我们来讨论一下优先级队列和堆的区别堆是一种数据结构，是一种非常确定的数据结构，堆顶是最值，就像链表、队列、栈这种数据结构。

而优先级队列是一种抽象的数据类型，只给了是什么的解释(what)，没有给具体实现(how)，只不过恰巧优先级队列大部分情况都是用堆实现的。

温馨提示如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请关注ACM算法日常。

点赞的时候，请宠溺一点