C++优先队列(priority_queue)简析和使用

基本操作

跟队列的基本操作一样，也包含在queue这个头文件。
1. empty() 如果队列为空返回真
2. pop() 删除对顶元素
3. push() 加入一个元素
4. size() 返回优先队列中拥有的元素个数
5. top() 返回优先队列对顶元素
注意：默认优先队列先出队的元素为优先级最高的元素，在默认的int型中先出队的是最大的元素。标准库默认使用元素类型的 < 操作符来确定它们之间的优先级关系

实现方式

1. 基本数据类型的优先队列

默认是从大到小

1
2
3
4
5
6
7
8
9
10

int a[] = {4,7,3,8};
priority_queue<int> intQ;
for (int i=0; i<4; i++) {
    intQ.push(a[i]);
}
while (!intQ.empty()) {
    cout<<intQ.top()<<" ";
    intQ.pop();
}
cout<<endl;

输出：8 7 4 3

从小到大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int a[] = {4,7,3,8};

//priority_queue另一种实现方式
//第一个参数是数据类型
//第二个参数是容器类型，默认用vector
//第三个参数是比较函数类型，默认是less<>,这里可以传入仿函数
priority_queue<int,vector<int>,greater<int>> intQ;
for (int i=0; i<4; i++) {
    intQ.push(a[i]);
}
while (!intQ.empty()) {
    cout<<intQ.top()<<" ";
    intQ.pop();
}
cout<<endl;

输出：3 4 7 8

2. 自定义数据类型的优先队列

在自定义的结构体内重载<运算符

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

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
    int val;

    Node(int v)
    :val(v)
    {

    }
    //在结构体内重载<运算符
    bool operator<(const Node &a)const{
        return val>a.val;//val小的优先级高
    }
};
int main(int argc, const char * argv[]) {
  priority_queue<Node> q;
   Node n1(3);
    Node n2(4);
    Node n3(1);

    q.push(n1);
    q.push(n2);
    q.push(n3);

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

    return 0;
}

输出： 1 3 4

在结构体外重载<操作符

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

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
    int val;

    Node(int v)
    :val(v)
    {

    }
};

//重载<操作符
bool operator<(Node a,Node b){
    return a.val > b.val ;
}

int main(int argc, const char * argv[]) {
  priority_queue<Node> q;

    Node n1(3);
    Node n2(4);
    Node n3(1);

    q.push(n1);
    q.push(n2);
    q.push(n3);

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

    return 0;
}

输出：1 3 4

自定义比较函数

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

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
    int val;

    Node(int v)
    :val(v)
    {

    }
};

//仿函数
struct Compare {
   //重载()操作符
    bool operator()(Node a,Node b){
        return a.val > b.val;//val小的优先级高
    }
};

int main(int argc, const char * argv[]) {
    priority_queue<Node,vector<Node>,Compare> q;
    Node n1(3);
    Node n2(4);
    Node n3(1);

    q.push(n1);
    q.push(n2);
    q.push(n3);

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

    return 0;
}

输出：1 3 4

Comments