0

第一季度

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

所以我不明白为什么在元素之前会输出最后一个意思。我错过了什么？

第二季度

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

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

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

我希望该比较函数与比较类联合，但将重新声明 operator() 函数。

可以统一代码吗？

4

1 回答 1

2

Q1 主要是术语冲突；排序关系a < b通常说“a在之前排序b”，但在 priority_queue 中，a < b意味着“a优先级低于b”。在优先顺序中也是
如此。（即优先顺序与排序关系的顺序相反。）ba

这是关于第二季度的一项建议；一个类模板。

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;
}
于 2021-09-27T08:46:53.303 回答