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

Question

Q1

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

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

But because the priority queue outputs largest elements first, the elements that "come before" are actually output last.

我是这样学习堆实现的。

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

所以我不明白为什么 come before element 会输出 last mean。我错过了什么吗？

Q2

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

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 应该是最小堆，首先弹出最少的元素。代码工作正常。

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

我希望将比较函数联合到比较 class，但 operator() 函数将被重新声明。

是否可以统一代码？

Answer 1

Q1主要是术语冲突；排序关系 a < b 通常表示“a 在 b 之前排序”，但在 priority_queue 中，a < b 表示“a 具有较低的顺序”优先于 b".
因此 b 在优先顺序中位于 a 之前。（即优先顺序与排序关系的顺序相反。）

这里有一个关于Q2的建议；一个 class 模板。

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;
}

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

Q1 : priority_queue "come before means output last", Q2 : custom compare with sort and priority_queue

c++

heap

priority-queue

custom-compare