If you want priority_queue to have the smallest element at the top() you write:
auto cmp = [&](const Node& lhs, const Node& rhs)
{
return lhs > rhs;
};
std::priority_queue<Node, std::vector<Node>, decltype(cmp)> pq(cmp);
However, if you want to use std::sort on a vector, and have the smallest element be at index 0, you write:
auto cmp = [&](const Node& lhs, const Node& rhs)
{
return lhs < rhs;
};
std::sort(vec.begin(), vec.end(), cmp);
Notice that in the lambda cmp the comparison signs are different? That’s annoying… So watch out for that, and don’t use the same functions between these two containers.
A useful mnemonic is:
– For std::sort left is up
– For std::priority_queue left is down
In other words, when you are using std::sort the left hand side is smaller than right hand side, and it will be “up” in the array, meaning lower values will be towards the lower indices. For priority queue, left is down, that means that greater values (lhs) will be at the bottom, so you can just visualize rotating the comparison one way or the other to remember how items will be sorted.
Leave a Reply