STL之优先级队列(priority_queue)

前言

最近在刷算法题的时候遇到了需要使用堆来解决的问题(尤其是TOP k 问题)，所以想把这些方法总结一下，防止后面忘记了还得到处找资料。希望能帮助到大家
参考链接1
参考链接2

堆(heap)的介绍

对通常是一个可以被看做一棵树的数组对象，满足两个条件：1，堆中的某个结点的值总是不大于或者不小于其父结点的值 2，堆是一颗完全二叉树
根结点最大的数叫做大根堆，最小的叫做小根堆。
堆排序中建堆的时间复杂度为O(n)
在C++ STL中没有堆的数据结构，所以借助其中的 priority_queue(默认是大根堆)

priority_queue

常用的方法如下：

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
1
2
3
4
5
6
7

priority_queue使用

1. 定义：priority_queue ，priority_queue属于是容器适配器，需要指定底层的容器，所以第一个参数Type是queue里面存的数据的类型，第二个参数Container是要使用的底层容器(一般是vector)，Functional 就是比较的方式.
2. 当数据是基本数据类型时可以使用默认的比较方式，使用如下：

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;
//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。
//其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）
1
2
3
4
5
6

当使用自定的数据类型时，比较方式的写法

1. lambda函数（如果有不清楚的可以参考我的这篇文章：c++11新特性）

auto cmp = [](pair<int, int> left, pair<int, int> right) -> bool { return left.second > right.second; };
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)>  pri_que(cmp);
1
2

2. 仿函数实现(最常用)

class mycomparison {
public:
    bool operator()(const pair<int, int>& left, const pair<int, int>& right) {
        return left.second > right.second;
    }
};
priority_queue<pair<int,int>,vector<pair<int, int>>,mycomparison> pri_que2;
1
2
3
4
5
6
7

3. 在自定义类型的类或者结构体中，重载运算符

struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
}
priority_queue<tmp1> pri_que3;
1
2
3
4
5
6
7
8
9
10
11