Q1 ： priority_queue "come before means output last" ， Q2 ： 自定义比较排序和priority_queue

Question

Q1

https://en.cppreference.com/w/cpp/container/priority_queue

我正在查看此网页，在模板参数部分中比较是这样说的。

但是由于优先级队列首先输出最大的元素，因此 "之前"的元素实际上是最后输出的。

我学会了这样的堆实现。

parent node : i / 2 
left child node : i * 2 
right child node : i * 2 + 1

因此，如果我制作最大堆，那么数组将像这样制作。

https://media.vlpt.us/images/emplam27/post/4a05c33e-2caf-4b28-964c-7019c13ff34b/%ED%9E%99%20-%20%EB%B0%B0%EC%97%B4%EB%A1%9C.png

所以我不明白为什么在元素之前输出最后一个平均值。 我错过了什么吗？

第 2 季度

我想为排序和优先级队列制作自定义比较对象。 这是我的代码。

struct Compare
{
bool operator()(vector<int>& l, vector<int>& r) { return r[1] < l[1]; }
};
bool compare(vector<int>& l, vector<int>& r) { return l[0] < r[0]; }
int solution(vector<vector<int>> jobs) {
sort(jobs.begin(), jobs.end(), compare);
priority_queue<vector<int>, vector<vector<int>>, Compare> jobQueue;
}

我想要这种排序应该是升序的，priority_queue应该是最小堆以首先弹出最少的元素。 并且代码工作正常。

但我觉得代码有点不漂亮，类似的比较被分开了。

我希望将比较函数联合到比较类，但运算符()函数将被重新声明。

是否可以统一代码？

Answer 1

Q1 主要是术语冲突;排序关系通常a < b说"a在b之前排序"，但在priority_queue中，a < b表示"a的优先级低于b".
所以b在优先级顺序中排在a之前。(也就是说，优先级顺序与排序关系的顺序相反。

下面是关于 Q2 的一个建议;类模板。

template<typename T, size_t index>
struct Compare
{
bool operator()(vector<int>& l, vector<int>& r) { return order(l[index], r[index]); }
T order;
};
using SortedOrder = Compare<std::less<int>, 0>;
using PriorityOrder = Compare<std::greater<int>, 1>;
int solution(vector<vector<int>> jobs) {
sort(jobs.begin(), jobs.end(), SortedOrder());
priority_queue<vector<int>, vector<vector<int>>, PriorityOrder> jobQueue;
return 0;
}