C++ STL heap用法

头文件：
#include <algorithm>

堆操作方法-更底层，支持复杂度O(n)的直接建堆。
数据结构不改变，是直接将原先容器中的元素order变成符合堆定义的order

1.1 默认大顶堆，即cmp位置传入 "less<>{}"
vector<int> v { 3, 2, 4, 1, 5, 9 };
// 建堆：传入iterator
// make_heap(iterator::left, iterator::right, cmp = less<>);
make_heap(v.begin(),v.end()); //默认max-heap
// after make_heap, v: 9 5 4 1 2 3

// 弹出：先pop_heap再pop_back
pop_heap(v.begin(),v.end());
// after pop_heap, v: 5 3 4 1 2 9 
// 把堆顶元素放到堆尾去了
// 此时非堆尾元素构成一个堆
int top = v.back; // top = 9
v.pop_back();
// v仍然是一个vector<int>，支持pop_back
// after removing the former top element, v: 5 3 4 1 2

// 压入：先push_back再push_pop
v.push_back(6);
push_heap(v.begin(),v.end());

1.2 快捷改成小顶堆
1.2.1 先把数据都添加负号再建堆
1.2.2 cmp位置传入 "greater<>{}"
make_heap(v1.begin(), v1.end(), greater<>{});
//注意pop_heap和push_heap时同样也要传
pop_heap(v1.begin(), v1.end(), greater<>{});
push_heap(v1.begin(), v1.end(), greater<>{});

1.3 传入其他cmp自定义

#include <queue>

封装的更好。但是不支持直接建堆。
数据结构改为优先队列类型,与vector<>接口不能共用。

2.1 默认是传入less<>，是最大堆
priority_queue<int> res;
res.push(x);

2.2 可以传入greater<> 改成最小堆，或将数据添加负号
priority_queue<int, vector<int>, greater<> > res;
res.push(x);
// 或
priority_queue<int> res;
res.push(-x);

2.3 自定义结构
struct S{
    int key, val;
    //一定是重写 < 操作符！！
    bool operator<(const &S other){
        return val < other.val; 
        // 或其他的判别方式，但反正大的那个意味着更高的优先级
    }
priority_queue<S> res;
res.push({key,val});//此时便会自动用S中重写的<当作cmp函数去排序
}