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

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

i'm looking this webpage and in template parameters section Compare says like this.

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

i learned that heap realization like this.

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

so if i make max heap then array will made like this.

https://media.vlpt.us/images/emplam27/post/4a05c33e-2caf-4b28-964c-7019c13ff34b/힙 - 배열로.png

so i can't understand why come before element will output last mean. did i miss something?

i want to make custom compare object for sort and priority queue. here is my code.

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

i was wanted that sort should be ascending, and priority_queue should be min heap to pop least element first. and code work right.

but i feel that code is little unpretty that similar compare were separated.

i want that compare function united to Compare class, but operator() function will be redeclared.

is it possible to unite code?

CodePudding user response：

Q1 is mostly a terminology clash; the ordering relation a < b usually says "a is ordered before b", but in a priority_queue, a < b means "a has a lower priority than b".
So b is before a in the priority order. (That is, the priority order is the opposite of the ordering relation's order.)

Here is one suggestion regarding Q2; a class template.

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