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

pair 将两个数据（经常为不同数据类型）组合成一组数据。pair 的实现是一个结构体，主要的两个成员变量是 first、second。pair 的比较规则：先比较第一个元素，第一个相等比较第二个。

hnjzsyjyj

12112人浏览 · 2020-10-05 16:41:39

hnjzsyjyj · 2020-10-05 16:41:39 发布

【算法分析】
一、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() 交换内容

3. 优先队列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;
}

/*
out:
4 3 2 1 0
0 1 2 3 4
cbd abcd abc
*/

三、用 pair 做优先队列 priority_queue 元素的例子
pair 的比较规则：先比较第一个元素，第一个相等比较第二个。

#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;
}

/*
out:
6 1
1 5
1 2
*/