使用 greater 和 vector 声明优先级队列

Question

谁能解释一下这个声明的含义：

typedef pair<long long, int> PII;
priority_queue<PII, vector<PII>, greater<PII> > Q;

是作为long long和int对的优先级队列还是别的？能否请有人也解释一下这里的 greater<PII> 是什么？

Answer 1

这声明了一个包含 std::pair<long long, int> 个实例的 std::priority_queue，其中 std::vector<std::pair<long long, int>> 是优先级队列的底层容器（因为它是一个容器适配器）。

std::greater<std::pair<long long, int>>用作队列的Comparator函数对象，检查LHS对是否大于RHS对。参考如下：

http://en.cppreference.com/w/cpp/utility/functional/greater

Answer 2

这里使用greater意味着较低的值被认为具有较高的优先级并且更早地从优先级队列中出来。默认使用less，值越大优先级越高。

对按字典顺序排列； (1, 3) 在 (2, 1) 之前和 (1, 2) 之后。

Answer 3

这是在 C++ 中创建最小堆的方法。

typedef pair<long long, int> PII;
priority_queue<PII, vector<PII>, greater<PII> > Q;