CODEWITHSUNDEEP
c++sortingpointerspriority-queue
Michał Młudzik
Michał Młudzik

Reputation: 55

Priority queue sorting pointers to objects that change value. C++

I have a queue that consists of pointers. It is sorted by node->p. Problem appears when I want to update priorities of elements inside the queue and then pop them in sorted order.

#include <iostream>
#include <queue>

using namespace std;

struct node {
    int p;
    int d;
};

struct LessThanByP
{
    bool operator()(const node * lhs, const node * rhs) const
    {
        return lhs->p > rhs->p;
    }
};

int main(int argc, const char * argv[])
{
    priority_queue<node *, deque<node *>, LessThanByP> q;

    node *node1, *node3, *node2;
    node1 = new node;
    node2 = new node;
    node3 = new node;

    node1->p = 2;
    node2->p = 1;
    node3->p = 0;

    node1->d = 3;
    node2->d = 4;
    node3->d = 5;

    q.push(node3);
    q.push(node2);
    q.push(node1);

    node1->p = 1;
    node2->p = 2;
    node3->p = 3;

    while(!q.empty())
    {
        cout << q.top()->d << endl;
        q.pop();
    }

    return 0;
}

I am looking for a way to sort the queue after changing priorities of its elements.

Result:

5
3
4

Expected result:

3
4
5

Upvotes: 0

Views: 1444

Answers (1)

nwp
nwp

Reputation: 9991

You cannot update the priority like that. The priority_queue assumes that objects do not suddenly change their value / order. To update a value in the priority_queue you need to remove it from the queue, change it and then insert it again.

Upvotes: 5

Related Questions