用pair做优先队列priority_queue元素的例子

admin管理员组

文章数量:1623789

【算法分析】

一、pair
pair将两个数据（经常为不同数据类型）组合成一组数据。
pair的实现是一个结构体，主要的两个成员变量是first、second。

pair的常见构造方法如下：
1.pair<T1, T2> p1;
创建一个空的pair对象，它的两个元素分别是T1和T2类型，然后赋值初始化。实例如下：

#include<bits/stdc++.h>
using namespace std;
int main() {
	pair<int,double> p1;
	p1.first=1;
	p1.second=2.5;
	cout<<p1.first<<" "<<p1.second<<endl;
	return 0;
}

输出为：1 2.5

2.pair<T1, T2> p1(v1, v2);
创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。实例如下：

#include<bits/stdc++.h>
using namespace std;
int main() {
	pair<string, double> p2("Algorithm", 56.8);
	cout<<p2.first<<" "<<p2.second<<endl;
	return 0;
}

输出为：Algorithm 56.8

3.make_pair(v1, v2);
以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。实例如下：

#include<bits/stdc++.h>
using namespace std;

int main(){
	int age=8;
	string name="James";
	pair<int,string> p3;
	p3=make_pair(age,name);
	cout<<p3.first<<" "<<p3.second<<endl;
	return 0;
}

输出为：8 James

二、优先队列priority_queue
优先队列priority_queue，本质上是用堆实现的，可用于实现“堆优化的Dijkstra算法”。
1.基本语法

·升序队列，小根堆：priority_queue <int,vector<int>,greater<int> > p;

·降序队列，大根堆：priority_queue <int,vector<int>,less<int> >q;

·对于基础数据类型，默认是大顶堆：priority_queue<int> r;    //等同于 priority_queue<int, vector<int>, less<int> > r;

2.基本操作

优先队列priority_queue和队列基本操作相同:

top 访问队头元素

empty 队列是否为空

size 返回队列内元素个数

push 插入元素到队尾 (并排序)

emplace 原地构造一个元素并插入队列

pop 弹出队头元素

swap 交换内容

优先队列priority_queue的常见实现如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
	priority_queue<int> a;
	priority_queue<int,vector<int>,greater<int> > b;
	priority_queue<string> c;
	for (int i=0;i<5;i++){
		a.push(i);
		b.push(i);
	}
	
	while (!a.empty()){
		cout<<a.top()<<" ";
		a.pop();
	}
	cout<<endl;

	while(!b.empty()){
		cout<<b.top()<<" ";
		b.pop();
	}
	cout<<endl;

	c.push("abc");
	c.push("abcd");
	c.push("cbd");
	while (!c.empty()){
		cout<<c.top()<<" ";
		c.pop();
	}
	cout<<endl;
	return 0;
}

输出为：
4 3 2 1 0

0 1 2 3 4

cbd abcd abc

【程序代码】

#include<bits/stdc++.h>
using namespace std;

int main() {
	priority_queue<pair<int, int> > a;
	pair<int,int> b(1,5);
	pair<int,int> d(1,2);
	pair<int,int> c(6,1);

	a.push(d);
	a.push(c);
	a.push(b);

	while (!a.empty()) {
		cout<<a.top().first<<" "<<a.top().second<<endl;
		a.pop();
	}

	return 0;
}

【程序输出】
pair的比较规则：先比较第一个元素，第一个相等比较第二个。
6 1
1 5
1 2


【参考文献】
https://blog.csdn/sevenjoin/article/details/81937695
https://wwwblogs/huashanqingzhu/p/11040390.html
https://www.sohu/a/256022793_478315

本文标签： 队列例子元素pairpriorityqueue