CODEWITHSUNDEEP
c++queuepriority-queueminmax-heap
eternityparadigm
eternityparadigm

Reputation: 384

Anomaly in Priority Queue Custom Sort in C++

I went through a couple of StackOverflow and Codeforces articles for custom sorting priority queues in C++. By default the C++ implementation is a MaxHeap , so it would output elements in decreasing order. I minor tweak adding greater<int> would pop ascendingly. I tried this out using my own comparator function, as below:

#include<bits/stdc++.h>
using namespace std;
class comp{
    public:
bool operator()(const int &a,const int &b){
        return a>b;
    }
};
int main(){
    priority_queue<int,vector<int>,comp> pq;
    pq.push(5);
    pq.push(1);
    pq.push(8);
    while(!pq.empty()){
        cout<<pq.top()<<" ";
        pq.pop();
    }
    return 0;
}

This gives the output as expected : 1 5 8

But if I change this to:

#include<bits/stdc++.h>
using namespace std;
class comp{
    public:
bool operator()(const int &a,const int &b){
        if(a>b)
            return true;
    }
};
int main(){
    priority_queue<int,vector<int>,comp> pq;
    pq.push(5);
    pq.push(1);
    pq.push(8);
    while(!pq.empty()){
        cout<<pq.top()<<" ";
        pq.pop();
    }
    return 0;
}

The output changes to : 8 1 5

I'm somehow not able to get this, any help is much appreciated.

Upvotes: 0

Views: 140

Answers (1)

Alberto
Alberto

Reputation: 12899

I would suggest you to read the compiler warnings... you will see that bool operator()(const int &a,const int &b) if a<=b doesn't have a return statement... and that's Undefined Behavior

Instead you should do this:

#include<bits/stdc++.h>
using namespace std;
class comp{
    public:
    bool operator()(const int &a,const int &b){
        if(a>b)
            return true;
        /* else */ return false;
    }
};
int main(){
    priority_queue<int,vector<int>,comp> pq;
    pq.push(5);
    pq.push(1);
    pq.push(8);
    while(!pq.empty()){
        cout<<pq.top()<<" ";
        pq.pop();
    }
    return 0;
}

Upvotes: 2

Related Questions