队列是先进先出的一种逻辑数据结构,优先队列是可以按照指定顺序输出元素的一种队列。它的底层实现是堆(堆的底层实现是用一个数组来模拟一棵树,在面试中可能会让你在白板上写堆的底层实现)。
在c++中,已经定义好了优先队列的容器类,我们可以直接调用。
#include <queue>;
priority_queue<int> pq;
pq.push(num);
我们可以以下代码来进行测试:
#include <iostream>
#include <queue>
#include <ctime>
using namespace std;
int main() {
srand(time(NULL));//种子
priority_queue<int> pq;
for(int i = 0; i < 10; i ++)
{
int num = rand()%100;
pq.push(num);
cout<<"insert "<<num <<" in priority queue."<<endl;
}
while(!pq.empty())
{
cout<<pq.top()<<" ";
pq.pop();
}
return 0;
}
上面这段代码就是随机生成一些树,存入优先队列,然后再输出。通过输出的结果可以发现,c++默认的输出顺序是从大到小,即底层是以最大堆实现的。
如果想以从小到大的顺序输出,那该怎么办呢?
在c++中,我们在定义优先堆列的时候,需要多传入几个参数。
priority_queue<int, vector<int>, greater<int>> pq2;
第一个参数是存入的数据类型,第二个参数是底层的结构实现,通常情况下,我们的顶层实现都是以vector向量来实现,第三个参数是c++帮我们定义好的比较函数。默认情况下是less。
可以通过测试发现,输出的元素是从小到大的顺序。
通常情况下,我们使用最小堆和最大堆就可以解决大多数的问题了。
但在一些极特别的情况下,我们需要自定义大小的关系。这种情况下怎么办呢?
在c++中,我们可以使用自定义的comparator的priority queue来实现。
bool myCmp(int a, int b)
{
return a%10 <b%10; //比较个位数谁小
}
priority_queue<int, vector<int>, function<bool(int,int)>> pq3(myCmp);
通过测试可以看到输出的元素顺序。
至此,是优先队列的输出顺序定义,下面贴出上述三种情况的定义/测试的完成代码。
#include <iostream>
#include <queue>
#include <ctime>
using namespace std;
bool myCmp( int a , int b ){
return a%10 > b%10;
}
int main() {
srand(time(NULL));
// 默认的priority queue, 底层是最大堆
priority_queue<int> pq;
for( int i = 0 ; i < 10 ; i ++){
int num = rand()%100;
pq.push( num );
cout<<"insert "<<num<<" in priority queue."<<endl;
}
while( !pq.empty() ){
cout<<pq.top()<<" ";
pq.pop();
}
cout<<endl<<endl;
// 使用greater的priority queue, 底层是最小堆
priority_queue<int, vector<int>, greater<int>> pq2;
for( int i = 0 ; i < 10 ; i ++){
int num = rand()%100;
pq2.push( num );
cout<<"insert "<<num<<" in priority queue."<<endl;
}
while( !pq2.empty() ){
cout<<pq2.top()<<" ";
pq2.pop();
}
cout<<endl<<endl;
// 使用自定义Comparator的priority queue
priority_queue<int, vector<int>, function<bool(int,int)>> pq3(myCmp);
for( int i = 0 ; i < 10 ; i ++){
int num = rand()%100;
pq3.push( num );
cout<<"insert "<<num<<" in priority queue."<<endl;
}
while( !pq3.empty() ){
cout<<pq3.top()<<" ";
pq3.pop();
}
return 0;
}
网友评论