0

In the code given below, I am trying to keep some values in priority_queue sorted accordingly their key values, which are stored in the "key" vector. And then, I am changing the key values to see if the comparator working properly or not. Here, when I change the key[8] to 10, value 8 changes its position in the queue correctly. But when I changed the key[2] to -1, it changed it's position in the queue, but not correctly. It should be positioned at the top of the queue, as it's key value is the smallest, but it's not.

Is my way of writing the code of the comparator wrong? Or, It's something else that I am not doing correctly?

I want to know the correct way to modify the comparator of priority queue if I want to sort values in ascending order accordingly to their key values.

enter image description here

#include <bits/stdc++.h>
using namespace std;
vector <int> key(1000);
struct comp{
    bool operator()(int a,int b)const{
        return key[a]>key[b];
    }
};
int main()
{
    priority_queue <int,vector<int>,comp> q,temp;
    for(int a=0;a<10;a++){
        int n=rand()%16;
        key[a]=n;
        q.push(a);
    }
    while(!q.empty()){
        temp=q;
        while(!temp.empty()){
            cout<< temp.top() << "(" << key[temp.top()] << ") ";
            temp.pop();
        }
        cout<<endl<<endl;
        int u,v;
        cin>> u >> v;
        key[u]=v;
    }
    return 0;
}
Sadman Rizwan
  • 189
  • 1
  • 2
  • 14
  • 6
    Where did you pick up the horrible `#include ` habit? That's a serious question. Beginners never did this until about a year ago. – Christian Hackl Apr 02 '17 at 16:19
  • 1
    it's a better idea to not include a code in an Image, when asking a question. – HDJEMAI Apr 02 '17 at 16:21
  • Does it create any problem? I actually use this to save time during programming contests. @Hackl – Sadman Rizwan Apr 02 '17 at 16:26
  • I actually included image to show the console output. I pasted the code below the image anyway. @H.DJEMAI – Sadman Rizwan Apr 02 '17 at 16:27
  • you can have what you want using `priority_queue ,std::greater> q,temp;` ? – HDJEMAI Apr 02 '17 at 16:45
  • `std::priority_queue` does not support decrease key operation; so you need to do a little more work to get this to work. Check my answer below. – Chintak Apr 02 '17 at 16:46
  • It will not sort values according to the key value.It will sort according to inserted values. @H.DJEMAI – Sadman Rizwan Apr 02 '17 at 16:47
  • 2
    [Why should I not #include ?](http://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [Why is “using namespace std” considered bad practice?](http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). Used together they place virtually the entire standard library into the global namespace. This means that all of a sudden there are a lot of identifiers with very common names in the global namespace where they could collide with and replace your program's identifiers. – user4581301 Apr 02 '17 at 16:53
  • You are pushing the index rather than the value no ? in `q.push(a);` should be `q.push(n);` ? – HDJEMAI Apr 02 '17 at 17:08
  • No, I want to sort indexes according to the key value of those indexes. @H.DJEMAI – Sadman Rizwan Apr 02 '17 at 17:11
  • @SadmanRizwan: What are those "programming contests" I hear about? They cannot be about producing useful code or about demonstrating that you can produce useful code, if they encourage you to produce bad code by typing fast. This rules out job interviews or participation in open-source projects. If they are some kind of game, then I think they should still make portable code part of the rules. In any case, please convert your programming-game code to real code when you post questions here on Stack Overflow. – Christian Hackl Apr 02 '17 at 17:25
  • @ChristianHackl The `#include using namespace std;` combo has made it onto HR filter lists. If it shows up in sample code, the resume goes into the waste bin without further examination. Sucks because it eliminates some programmers who could be good if trained out of sloppy habits, but there are a lot of programmers out there who aren't sloppy. – user4581301 Apr 02 '17 at 17:31
  • @SadmanRizwan recommend removing the random number generation while testing. It's harder to check for improvements in the code when the numbers keep changing. Have you added a few simple `cout`s to see if numbers are going into the queue the way you want? – user4581301 Apr 02 '17 at 17:35
  • 1
    @user4581301: That's only a problem if you actually intend to hire a complete beginner in order to train him or her on the job. I don't see any problem with using such a filter if you are looking for a senior developer. Reviewing job applications costs time and money. – Christian Hackl Apr 02 '17 at 17:39

2 Answers2

0

You never changed q. You made a copy of q in temp but never did anything to q.

kjpus
  • 509
  • 4
  • 8
0

The intent and the code are reasonable enough, but the issue is much more fundamental. The problem is that std::priority_queue does not support decrease key operation out-of-the-box.

In order to perform such operations, you would need to manually maintain the list of keys and call std::make_heap, std::push_heap from <algorithm>.

See this for a more detailed answer: https://stackoverflow.com/a/9210662/1045285

As a side note, consider instead including:

#include <priority_queue>
Community
  • 1
  • 1
Chintak
  • 365
  • 4
  • 14