priority_queue 大顶堆与小顶堆的用法 & 常见数据结构时间复杂度

1.创建堆

　　a.创建以内置类型(int,float等)为元素的堆.

#include <queue>

priority_queue<int> big;　　　　// 大顶堆
priority_queue<int, vector<int>, greater<int> > small;　　// 小顶堆

之后就可以对其使用队列的操作,比如push和pop.

　　b.创建以结构体为元素的堆

方法一:

编写比较函数.

struct node {
    int val, num, ...;　　　　// 自定义一个结构体
};
struct cmp {
    bool operator()(const node &a, const node &b) { return a.val > b.val; }　　　　// 花括号内编写比较函数
};
priority_queue<node, vector<node>, cmp> q;

这样就创建了一个以结构体node为元素,以cmp为比较函数的小顶堆,如果想要创建大顶堆,只需要把比较函数中的大于号改为小于号.

除了编写比较函数外还可以重载运算符,见下面的链接.

// 需要考虑到精度问题,以下面为例
// 比较平面上点的坐标大小,比较大小时先比较横坐标,再比较纵坐标
// 使用了重载运算符方法

struct poi {int x, y;};
const double eps = 1e-8;
bool operator <(const poi &a, const poi &b) { return a.x + eps < b.x || a.x < b.x + eps && a.y < b.y; }

方法二(推荐):

重载运算符.

例如,计算最小生成树时想要按照边的权大小升序排列,只需要将存边的结构体定义为:

struct E {
    int from, to, wei;
    bool operator<(E &other) const { return wei < other.wei; }
};

之后就可以如同内置类型一般对其进行排序,建堆等.这种方法显然比写比较函数简洁的多.

(更多创建结构体堆的方法见https://www.cnblogs.com/flipped/p/5691430.html)

2.复杂度: