Priority Queue

[keeda]

Hi,

I wish to implement a priority queue and I need to create it with structures, as in I will be inserting structures into the queue and I wish to keep it sorted(ascending order) it according to one of the structure elements.

How can this be done?

Any pointers will be appreciated!

eg: I have :
structure node{

string name;
int cost;
};

I want to keep my queue of structures sorted as per lowest cost to highest cost.

Thanks

[vijayan121]

Either overload operator< for node or write a binary predicate to compare nodes. eg.

struct compare_cost
{
    bool operator() ( const node& a, const node& b ) const
    { return a.cost < b.cost ; }
};

If you just need a priority queue, just use std::priority_queue<> std::priority_queue< node, std::deque<node>, compare_cost > node_pq ; If you really need to keep a sorted sequence at all times (expensive), use a sequence container and the std::lower_bound algorithm.

void insert_ordered( std::list<node>& seq, const node& item )
{
    seq.insert( std::lower_bound( seq.begin(), seq.end(),
                                  item, compare_cost() ), item ) ;
}