优先队列与set区别

1、优先队列

优先队列是不同于先进先出队列的另外一种队列,他每次从对列中取出的是具有最高优先级的元素;

优先队列有最小优先队列和最大优先队列。


2、C++ STL中的优先队列

(1)最大优先队列:

priority_queue<int> pq;

(2)最小优先队列

priority_queue<T,vector<T>,greater<T>>pq;


3、注意:

(1)可以指定容器、使用自定义的结构体

(2)默认容器是vector

(3)默认的优先队列是最大优先队列。


4、提供接口:

empty() 如果优先队列为空,则返回true;

top() 返回最高优先级的元素

pop()删除最高优先级的元素

push()加入一个元素

size() 返回优先队列中的元素个数


5、优先队列与set区别

(1)、set默认是从小到大输出的,而priority_queue默认是从大到小。


6、代码

#include<iostream>
#include<functional>
#include<queue>
#include<set>
using namespace std;

struct node
{
	int priority;
	int value;
};

bool operator< (node n1, node n2)
{
	return n1.priority < n2.priority;
}


int main()
{
	const int len = 5;
	int i;
	int a[len] = {3,5,9,6,2};
	
	//示例1
	priority_queue<int> qi;
	set<int> testset;

	for(i = 0; i < len; i++)
	{
		qi.push(a[i]);
		testset.insert(a[i]);
	}

	cout<<"priority_queue member:";
	for(i = 0; i < len; i++)
	{
		cout<<qi.top()<<" ";
		qi.pop();
	}

	cout<<endl;
	//set是从小到大输出的,而priority_queue是从大到小。
	cout<<"set member:";
	for (set<int>::iterator it = testset.begin(); it != testset.end(); ++it)
	{
		cout<<*it<<" ";
	}

	cout<<endl;
	
	//示例2
	priority_queue<int, vector<int>, greater<int> >qi2;
	for(i = 0; i < len; i++)
	{
		qi2.push(a[i]);
	}
	cout<<"priority_queue member:";
	for(i = 0; i < len; i++)
	{
		cout<<qi2.top()<<" ";
		qi2.pop();
	}
	cout<<endl<<endl;
	
	
	//示例3
	priority_queue<node> qn;
	set<node> sn;
	node b[len];

	b[0].priority = 6; b[0].value = 1; 
	b[1].priority = 9; b[1].value = 5; 
	b[2].priority = 2; b[2].value = 3; 
	b[3].priority = 8; b[3].value = 2; 
	b[4].priority = 1; b[4].value = 4; 

	for(i = 0; i < len; i++)
	{
		qn.push(b[i]);
		sn.insert(b[i]);
	}
	
	for(i = 0; i < len; i++)
	{
		cout<<"priority_queue member:"<<qn.top().priority<<'\t'<<qn.top().value<<endl;
		qn.pop();
	}
	
	for (set<node>::iterator itor = sn.begin(); itor != sn.end(); ++itor)
	{
		cout<<"set member:"<<(*itor).priority<<'\t'<<(*itor).value<<endl;
	}

	return 0;
}


版权声明:本文为chenchong_219原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。