C++ 优先级队列(priority_queue)用法

要使用priority_queue需要先包含头文件#include<queue>，相比queue，优先队列可以自定义数据的优先级，让优先级高的排在队列前面。

优先队列的基本操作：

empty：查看优先队列是否为空

size：返回优先队列的长度

top：查看堆顶的元素

push：插入一个元素

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

pop：移除堆顶的元素

swap：交换两个优先队列的内容

模板定义：

template <class T, class Container = vector<T>, 
class Compare = less<typename Container::value_type> > class priority_queue;

T是数据类型。

Container是存储数据的容器类型，其存储的数据类型必须是T。默认的容器是vector，也可以使用deque。

Compare是进行比较的方法，对于comp(a,b)这种比较方法，如果a的排序是在b之前，那么应该返回true。对于默认的比较方法是less<T>，即返回的是 a<b。对于堆中任意一个节点node，它的父节点永远比它大。故在默认情况下，priority_queue是大顶堆。

1.基本操作的使用：

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

int main()
{
    int num[] = {10, 30, 20, 90, 120, 50};
    priority_queue<int> pq1;
    priority_queue<int> pq2(num, num + 6);                            //默认情况大顶堆
    priority_queue<int, vector<int>, greater<int> > pq3(num, num + 6); //小顶堆

    cout << "pq1 is empty? " << (pq1.empty() ? "yes" : "no") << endl;
    cout << "the size of pq2 is " << pq2.size() << endl;

    cout << "the top of pq2 is " << pq2.top() << endl;
    cout << "the top of pq3 is " << pq3.top() << endl;

    pq1.push(30);
    cout << "the top of pq1 is " << pq1.top() << endl;
    pq1.emplace(10);

    pq1.pop();
    cout << "the top of pq1 is " << pq1.top() << endl;

    swap(pq1, pq2);
    cout << "the top of pq1 is " << pq1.top() << endl;
    cout << "the top of pq2 is " << pq2.top() << endl;
}

结果

pq1 is empty? yes
the size of pq2 is 6
the top of pq2 is 120
the top of pq3 is 10
the top of pq1 is 30
the top of pq1 is 30
the top of pq1 is 10
the top of pq1 is 120
the top of pq2 is 10

2.自定义对象的比较

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

class Node
{
public:
    int x, y;
    Node(int x, int y) : x(x), y(y) {}

    bool operator<(const Node &a) const		//方法1：重载运算符
    {
        return (x * x + y * y) < (a.x * a.x + a.y * a.y);
    }

    bool operator>(const Node &a) const
    {
        return (x * x + y * y) > (a.x * a.x + a.y * a.y);
    }
};

template <typename T>		//方法2：自定义比较方法，下面也是STL中greater<T>的实现方法
struct mycmp
{
    bool operator()(const T &a, const T &b) const
    {
        return a > b;
    }
};

int main()
{
    Node n1(1, 1);
    Node n2(3, 4);
    Node n3(2, 0);
    priority_queue<Node> pq1;	//大顶堆
    pq1.push(n1);
    pq1.push(n2);
    pq1.push(n3);
    while (!pq1.empty())
    {
        cout << pq1.top().x << "," << pq1.top().y << endl;
        pq1.pop();
    }
	cout<<endl;
    
    priority_queue<Node, vector<Node>, mycmp<Node> > pq2;	//小顶堆
    pq2.push(n1);
    pq2.push(n2);
    pq2.push(n3);
    while (!pq2.empty())
    {
        cout << pq2.top().x << "," << pq2.top().y << endl;
        pq2.pop();
    }
    return 0;
}

结果

3,4
2,0
1,1

1,1
2,0
3,4

C++ 优先级队列(priority_queue)用法

原文：https://www.cnblogs.com/WiatrY/p/15313310.html