c++优先队列小记_优先队列push

力扣遇到一道题，【前k个高频元素】，题解使用优先队列来解题的

1. 优先队列概念

1. 优先队列与普通队列的区别
   可以定义其中的数据优先级，让优先级高的排在队列的前边，优先出队。优先队列包括队列的基本操作，并添加了一个内部的排序，本质上是一个堆；

2.优先队列定义

priority_queue<Type, Container, Functional>

1. Type 就是数据类型
2. Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list)，STL里面默认用的是vector
3. Functional 就是比较的方式,当需要用自定义的数据类型时才需要传入这个参数，使用基本数据类型时，默认是大顶堆

//小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//大顶堆
priority_queue <int,vector<int>,less<int> >q;
//默认大顶堆
priority_queue<int> a;
1
2
3
4
5
6

实例1

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main()
{
	//小顶堆
	priority_queue<int, vector<int>, greater<int>> q1;
	//大顶堆
	priority_queue<int, vector<int>, less<int>> q2;
	//默认大顶堆
	priority_queue<int> q3;
	vector<int> Arr{ 3,1,2,7,4,3,8,8 };
	for (auto n : Arr)
	{
		q1.push(n);
		q2.push(n);
		q3.push(n);
	}
	cout << q1.top() << endl;  //1
	cout << q2.top() << endl;  //8
	cout << q3.top() << endl;  //8
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

实例2：
优先队列的内置函数在进行pair比较的时候，默认先比较第一个元素，第一个相等比较第二个；但是有些任务只需要根据第一个元素的比较结果，这就需要进行自定义比较方式；

priority_queue<pair<int, int> > a;
pair<int, int> b(1, 2);
pair<int, int> c(1, 3);
pair<int, int> d(2, 5);
a.push(d);
a.push(c);
a.push(b);
while (!a.empty()) 
{
   cout << a.top().first << ' ' << a.top().second << '\n';
   a.pop();
}
//输出结果为：
2 5
1 3
1 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

对于常规的数据类型不需要自己构建比较函数，使用队列的常用函数就可以满足要求；

常用函数

top()
pop()
push()
emplace()
empty()
size()
1
2
3
4
5
6

3. 自定义比较方式

#include<iostream>
#include<vector>
#include<queue>
using namespace std;


bool cmp1(pair<int, int>& m, pair<int, int>& n) {
	return m.second > n.second;
}
bool cmp2(pair<int, int>& m, pair<int, int>& n) {
	return m.second < n.second;
}
	
int main()
{
	//自定义比较方式小顶堆
	priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp1)> q1(cmp1);
	//自定义比较方式大顶堆
	priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp2)> q2(cmp2);


	pair<int,int> a(1, 3);
	pair<int, int> b(2, 6);
	pair<int, int> c(3, 4);
	q1.push(a);
	q1.push(b);
	q1.push(c);
	q2.push(a);
	q2.push(b);
	q2.push(c);
	cout << q1.top().first << " " << q1.top().second << endl;
	cout << q2.top().first << " " << q2.top().second << endl;
	return 0;
}

output:
1 3
2 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

补充emplace的用法

使用emplace操作
emplace、emplace_front、emplace_back分别对应insert、push_front和push_back。
但emplace都是构造而不是拷贝元素。emplace成员会使用传递的参数在容器管理的内存空间中直接构造元素。若参数为空，则调用元素的默认构造函数。

vector<pair<int,int>>  vec;
vec.emplace(1,1);//正确，emplace直接根据得到的参数来构造容器的元素
vec.push_back(1,1);//错误
vec.push(pair(1,1));//正确，先产生临时对象，然后让进容器
1
2
3
4

补充

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

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const    // 因为优先队列的默认比较器是大顶堆  所以这里需要实现大顶堆的比较器。 如果需要使用小顶堆就写为return x > a.x; 但是operator<不能变
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};

// 方法3
bool cmp(tmp1 a, tmp1 b)
{
    return b.x > a.x;
}

int main() 
{
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty()) 
    {
        cout << d.top().x << '\n';
        d.pop();
    }
    cout << endl;

    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(c);
    f.push(b);
    f.push(a);
    while (!f.empty()) 
    {
        cout << f.top().x << '\n';
        f.pop();
    }

    priority_queue<tmp1, vector<tmp1>, decltype(&cmp)> g(cmp);
    g.push(c);
    g.push(b);
    g.push(a);
    while (!g.empty()) 
    {
        cout << g.top().x << '\n';
        g.pop();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67