C++优先队列的用法与求集合的交集并集差集

曾经终败给现在 2022-08-03 03:12 59阅读 0赞

**优先队列**

头文件为include<queue>

定义方法为  priority\_queue<int> q;

这个数据结构中的元素可按照一定条件排列有序

默认为降序

例如：

#include<stdio.h>
 #include<queue>
 using namespace std;
 int main()
 {
 	int n,i,t;
 	while(scanf("%d",&n)!=EOF)
 	{
 		priority_queue<int> q;
 		for(i=0;i<n;i++)
 		{
 			scanf("%d",&t);
 			q.push(t);
 		}
 		while(!q.empty())
 		{
 			printf("%d ",q.top());
 			q.pop();
 		}
 		printf("\n");
 	}
 	return 0;
 }

也可以升序排列

只需将定义优先队列语句改为：priority\_queue<int, vector<int>, greater<int> > q;

例如：

#include<stdio.h>
 #include<queue>
 using namespace std;
 int main()
 {
 	int n,i,t;
 	while(scanf("%d",&n)!=EOF)
 	{
 		priority_queue<int, vector<int>, greater<int> > q;
 		for(i=0;i<n;i++)
 		{
 			scanf("%d",&t);
 			q.push(t);
 		}
 		while(!q.empty())
 		{
 			printf("%d ",q.top());
 			q.pop();
 		}
 		printf("\n");
 	}
 	return 0;
 }

也可以自定义优先级，按条件排序

struct node
 {
 friend bool operator< (node n1, node n2)
 {
 return n1.priority < n2.priority;
 }
 int priority;
 int value;
 };

在该结构中，value为值，priority为优先级。 
通过自定义operator<操作符来比较元素中的优先级。 
在示例3中输出结果为： 
优先级  值 
9          5 
8          2 
6          1 
2          3 
1          4

例如：

#include<stdio.h>
 #include<queue>
 #include<iostream>
 using namespace std;
 struct node
 {
 	friend bool operator< (node n1, node n2)
 {
 return n1.priority < n2.priority;
 }
 int priority;
 int value;
 };
 int main()
 {
 	int len=5,i;
 	priority_queue<node> qn;
 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]);
 cout<<"优先级"<<'\t'<<"值"<<endl;
 for(i = 0; i < len; i++)
 {
 cout<<qn.top().priority<<'\t'<<qn.top().value<<endl;
 qn.pop();
 }
 return 0;
 }

有没有感觉用法跟sort排序有点相似？

在某些情况下，使用优先队列会更优于set

优先队列会更快

可能是因为队列为线性结构，而set是树形结构吧

个人愚见，若有错误，还请指出。

**求集合的交集并集差集**

在算法头文件\#include<algorithm>中

就包含对两集合进行操作的函数

set\_union() 并集

set\_intersection() 交集

set\_difference() 差集

set\_symmetric\_difference() 对称差

merge() 合并

集合的类型可以是数组，list，vector

前提是两个集合已经有序

可用sort对vector进行排序，例如：sort(vec.begin(),vec.end());

在这里使用vector为例，求两个集合的差集

求差集并定要先求出两集合的交集和并集

code:

#include<stdio.h>
 #include<vector>
 #include<algorithm>
 using namespace std;
 int main()
 {
 	int n,m,i,t;
 	vector<int> v1,v2,v_union,v_inter,v_diff;
 	while(scanf("%d %d",&n,&m)!=EOF)	//n为第一个集合元素个数，m为第二个集合元素个数
 	{
 		v1.clear();
 		v2.clear();
 		v_union.clear();
 		v_inter.clear();
 		v_diff.clear();
 		for(i=0;i<n;i++)
 		{
 			scanf("%d",&t);
 			v1.push_back(t);
 		}
 		sort(v1.begin(),v1.end());	//对集合v1排序
 		for(i=0;i<m;i++)
 		{
 			scanf("%d",&t);
 			v2.push_back(t);
 		}
 		sort(v2.begin(),v2.end());	//对集合v2排序
 		set_union(v1.begin(),v1.end(),v2.begin(),v2.end(),back_inserter(v_union));	//求得两集合并集
 		set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),back_inserter(v_inter));//求得两集合交集
 		set_difference(v_union.begin(),v_union.end(),v_inter.begin(),v_inter.end(),back_inserter(v_diff));	//求得两集合差集
 		vector<int>::iterator it;
 		for(it=v_diff.begin();it!=v_diff.end();it++)	//迭代器it指向差集
 			printf("%d ",*it);
 		printf("\n");
 	}
 	return 0;
 }