C++优先队列

C++优先队列aaaazaiiazh转载自https://blog.csdn.net/u012804490/article/details/26241523优先队列优先队列(priority queue)亦即数据结构中的堆,是计算机科学中一类特殊的数据结构的统称。在队列中,调度程序反复提取队列中第一个作业并运行,因而实际情况中某些时间较短的任务将等待长时间才能结束,或某些不短小,但具有重要性的作…

aaaazai ia
zh

转载自https://blog.csdn.net/u012804490/article/details/26241523

优先队列

优先队列(priority queue)亦即数据结构中的,是计算机科学中一类特殊的数据结构的统称。在队列中,调度程序反复提取队列中第一个作业并运行,因而实际情况中某些时间较短的任务将等待长时间才能结束,或某些不短小,但具有重要性的作业,同样应当具有优先权。优先队列即为解决此类问题设计的一种数据结构。优先队列(堆)通常是一个可以被看做一棵树的数组对象。

优先队列中的常用函数:

empty()   如果优先队列为空,返回真

pop()     删除第一个元素

push(x)   添加一个元素x

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

top()     返回优先队列中有最高优先级的元素

例如:

 

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
	int i;
	priority_queue<int> q;
	// 向队列中添加元素
	q.push(4);    q.push(1);
	q.push(3);    q.push(5);
	q.push(6);    q.push(2);
	int len=q.size();    // 统计优先队列中元素的个数
	for(i=0;i<len;i++)
	{
		// top()返回优先级最高的元素
		// 在优先队列中,默认为大根堆,即默认元素大的优先级高
		printf("%d ",q.top()); 
		q.pop();   // 删除第一个元素,也即优先级最高的元素
	}
	printf("\n");
	if(q.empty())   // 此时该优先队列中元素已删除完
		printf("该优先队列为空\n");
	return 0;
}

输出结果为:

 

6 5 4 3 2 1

该优先队列为空

 

如果我们希望在优先队列中的较小的元素优先出队,该怎么做呢?

So easy!

我们只需将priority_queue<int> q;改为priority_queue<int,vector<int>,greater<int> > q;

但是,我们为什么这么做呢?其中的各个参数表示什么意思呢?

首先,第一个参数表示数据的类型,第二个参数保存该数据类型数据的容器(默认情况下以vector实现),第三个参数表示自定义的优先级规则(默认情况下为大根堆,元素大的优先级高)。greater表示数据优先级顺序是从小到大,另外greater也可以改成less,表示数据优先级顺序是从大到小。

注:优先队列其实也就是我们数据结构中学过的堆,默认情况下底层是以vector实现的heap!

 

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
	int i;
	priority_queue<int,vector<int>,greater<int> > q;
	// 向队列中添加元素
	q.push(4);    q.push(1);
	q.push(3);    q.push(5);
	q.push(6);    q.push(2);
	int len=q.size();    // 统计优先队列中元素的个数
	for(i=0;i<len;i++)
	{
		// top()返回优先级最高的元素
		// 在优先队列中,默认为大根堆,即默认元素大的优先级高
		printf("%d ",q.top()); 
		q.pop();   // 删除第一个元素,也即优先级最高的元素
	}
	printf("\n");
	if(q.empty())   // 此时该优先队列中元素已删除完
		printf("该优先队列为空\n");
	return 0;
}

运行结果:

 

1 2 3 4 5 6

该优先队列为空

greater变为less的这里不再验证,请有兴趣的童鞋自己验证!

 

拓展:
优先队列还可以将一个普通数组中的元素转化为优先队列的初始值!

代码如下:

 

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
	int a[6]={3,2,1,4,6,5};
	priority_queue<int> q(a,a+6);
	while(!q.empty())
	{
		printf("%d ",q.top());
		q.pop();
	}
	printf("\n");
	return 0;
}

运行结果:

 

6 5 4 3 2 1

代码2:

 

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
	int a[6]={3,2,1,4,6,5};
	priority_queue<int> q(&a[2],a+6);  // &a[2]表示以a[2]的地址为开始地址,a+6表示数组的结束地址
	while(!q.empty())
	{
		printf("%d ",q.top());
		q.pop();
	}
	printf("\n");
	return 0;
}

运行结果:

 

6 5 4 1
 

如果想自定义优先级并且数据类型不是基本数据类型,而是复杂数据类型,则必须重载其中的operator();

 

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef struct
{
	int a;
	int b;
}Node;
// 自定义优先级
struct cmp
{
	bool operator()(const Node &t1,const Node &t2)
	{
		return t1.b<t2.b;  // 相当于less,数据元素值大的优先级高
	}
};
int main()
{
	int i,n;
	scanf("%d",&n);
	Node *num=new Node[n];
	for(i=0;i<n;i++)
	{
		scanf("%d%d",&num[i].a,&num[i].b);
	}
	priority_queue<Node,vector<Node>,cmp> q(num,num+n);
	while(!q.empty())
	{
		printf("%d ",q.top().b);
		q.pop();
	}
	printf("\n");
	return 0;
}

输入:

 

3

3 8

5 6

4 7

输出结果:

8 7 6

今天的文章C++优先队列分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/12910.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注