C++ priority_queue使用方法

优先队列priority_queue

priority_queue是C++提供的优先队列，定义在头文件<queue>中，默认为最大优先队列
定义如下

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

模板形参

• T 存储元素类型

• Container 用于存储元素的底层容器 如std::vector<T>,std::vector<std::vector<T> >,也就是容器的类型，

• Compare 严格弱序的比较 (Compare) 类型

  对于自定义的compare函数，需提供严格弱序。对于比较函数，若返回true,说明left “小于” right
  比较时，若要左操作数先于右操作数弹出，则应该返回false。(因为priority_queue总是返回**“最大”**的)，若要右操作数先弹出，则应该返回true

常用成员函数

成员函数	作用
top	访问栈顶元素
empty	检查队列是否为空
size	返回容纳的元素数
push	插入元素，并对底层容器排序(自动完成)
pop	弹出队列第一个元素
emplace	原位构造元素并排序底层容器
swap	交换内容

使用

如不特殊

template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}
//简单使用(大顶堆)
//这里默认使用了std::less<T>，这是一个仿函数类，重载了()操作符
/*
constexpr bool operator()(const T &lhs, const T &rhs) const 
{
    return lhs < rhs; 
}
*/
std::priority_queue<int> q;
for(int n : {1,8,5,6,3,4,0,9,7,2}){
	q.push(n);
}
print_queue(q);
//输出 9 8 7 6 5 4 3 2 1 0 

//小顶堆
std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
for(int n : {1,8,5,6,3,4,0,9,7,2})
        q2.push(n);
print_queue(q2);

//输出 0 1 2 3 4 5 6 7 8 9

自定义比较函数

这里使用std::vector<std::vector<int>>作为底层容器，按二元组std::vector第一个坐标从小到大排序，若相同则第二个坐标从小到大排序

template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        auto temp = q.top();
        std::cout << temp[0] << " "<<temp[1]<<std::endl;
        q.pop();
    }
    std::cout << '\n';
}
//定义比较函数
//对于比较函数，若返回true,说明left是“小于” right的，
//priority_queue总是返回“最大”的，right就会优先被弹出
int main(){
    auto cmp = [](std::vector<int> left, std::vector<int> right) { 
        if(left[0] == right[0])
            return left[0] > right[0];
            return left[0] > right[0];
    };
    std::priority_queue<std::vector<int>, std::vector<std::vector<int>>, decltype(cmp)> q3(cmp);
    std::vector<std::vector<int>> arr{{3,4},{1,3},{5,7},{1,5},{9,4},{4,2},{3,5}};
    for(auto& n :arr){
        q3.push(n);
    }
    print_queue(q3);;
    return 0;
}
//输出
/*
1 3
1 5
3 5
3 4
4 2
5 7
9 4
*/