Custom compare operator for priority_queue

[fair sigil]

I am trying to create a max-heap of pair that will compare the first part of the pair and if they are equal it will not swap element? But still its accessing the smaller element first due to which my algorithm is not working, am i doing something wrong?

Compare function

class Comp{
    public:
    bool operator()(pair<int,int> &a , pair<int,int> &b){
return a.first > b.first;
    }
};

Usage

priority_queue<pair<int,int>,vector<pair<int,int>> , Comp> q;

Full code - https://pastecode.io/s/p4fw9ibw

[edgy parrot]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

[fading zenith]

The lack of const is suspicious, but I don't think it's a problem.

I don't know what t is.

How do you know it's accessing the smaller element first?

[iron spindle]

Priority queue is already a "max heap", in the sense that when you call the member function top you will get the maximum value

The way the custom comparison is used, is that whenever comp(a, b) evaluates true, a is considered smaller than b

Otherwise a is considered greater than or equal to b

If you want a "max heap" that only compares the first element of the pair, your custom comparator should still perform a "less than" (<) comparison

[iron spindle]

;compile

struct compare_first_less
{
    bool operator()(std::pair<int, int> const& lhs, std::pair<int, int> const& rhs) const
    {
        return lhs.first < rhs.first;
    }
};

struct compare_first_greater
{
    bool operator()(std::pair<int, int> const& lhs, std::pair<int, int> const& rhs) const
    {
        return lhs.first > rhs.first;
    }
};

std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, compare_first_less> q_less;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, compare_first_greater> q_greater;
for (int i = 0; i < 4; ++i)
{
    q_less.emplace(std::make_pair(i, 2*i));
    q_greater.emplace(std::make_pair(i, 2*i));
}

std::cout << "displaying q_less:\n";
while (!q_less.empty())
{
    auto const [first, second] = q_less.top();
    q_less.pop();
    std::cout << '(' << first << ", " << second << ")\n";
}

std::cout << "displaying q_greater:\n";
while (!q_greater.empty())
{
    auto const [first, second] = q_greater.top();
    q_greater.pop();
    std::cout << '(' << first << ", " << second << ")\n";
}

[timber crane]

Program Output

displaying q_less:
(3, 6)
(2, 4)
(1, 2)
(0, 0)
displaying q_greater:
(0, 0)
(1, 2)
(2, 4)
(3, 6)

slybach | 46ms | c++ | x86-64 gcc 13.2 | godbolt.org

[fair sigil]

I want it to access the larger element first having greater first element of the pair which is default behaviour of priority_queue

[fair sigil]

ok I thought the truth value will be dependent on the type of heap I am creating, like for max heap a.first should be > than b.first

the algo is working fine when I am performing it in white board as psuedo code, but not in code. I am misunderstanding some property of heap

[iron spindle]

It is dependent, that's the whole point of the sample code I provided

If you use a comparator that does "less than" you get a max heap
If you use a comparator that does "greater than" you get a min heap

The adaptor std::priority_queue is always a "max heap" which is why you have to reverse the order defined by the comparator if you want a "min heap"

It's a "max heap" over the ordering defined by the comparator

[fair sigil]

I am confuse now then why for a custom vector in decreasing order
this will work

bool customComparator(int a, int b) {
    return a > b; // For descending order, return true if a should come before b
}

shouldn't it be a<b like bool ```cpp
bool operator()(std::pair<int, int> const& lhs, std::pair<int, int> const& rhs) const
{
return lhs.first < rhs.first;
}

[iron spindle]

The comparator defines the order, and it always define it by returning true when the first argument is "smaller" than the second, no exception
Then for that order priority queue always pick out the "maximum" value to give you, in priority

That's why it's always a max heap and why people get confused by it

for this custom comparator

bool customComparator(int a, int b) {
    return a > b; // For descending order, return true if a should come before b
}

it defines an order on integers, so if you have a bunch of integers like 1 5 10 40
the order defined by the comparator would sort them in this order 40 10 5 1 with the first one being the "smallest" and the last one the "largest"

priority queue then always give you the last one, because it's always a max heap

if your comparator does the "usual" less than, then the ordering/sorting of that same set of integers would give you 1 5 10 40 instead, and priority queue would still give you the "maximum" one, aka the "last" one, which would fit the usual definition of maximum on integers

[fair sigil]

This is confusing, I'll try to understand

What I am not understanding is how returning true is valid in priority queue if a has higher priority than b.

class MaxHeapComparator {
public:
    bool operator()(int a, int b) {
        return a < b; // Returns true if a has higher priority than b
    }
};

[fair sigil]

ok I got it now. MaxHeap -> top priority comes first -> a<b makes sense b should be lowers in ranks ( 1st being highest rank ) but in vector a>b literally means a should be larger than b.