CODEWITHSUNDEEP
c++stl
russell
russell

Reputation: 3766

stl priority queue based on lower value first

I have a problem with stl priority queue.I want to have the priority queue in the increasing order,which is decreasing by default.Is there any way to do this in priority queue.

And what is the complexity of building stl priority queue.If i use quick sort in an array which takes O(nlgn) is its complexity is similar to using priority queue???

Plz someone ans.Advanced thanx.

Upvotes: 2

Views: 15212

Answers (6)

Himanshu Poddar
Himanshu Poddar

Reputation: 7779

You can use comparator class/struct to achieve the same in priority queue.

class CompareHeight 
{ 
    public:
        bool operator()(int &p1, int &p2) 
        {
            return p1 > p2; 
        } 
};

Now declare the priority queue as

priority_queue<int, vector<int>, CompareHeight> pq;

Upvotes: 0

Niloy Rashid
Niloy Rashid

Reputation: 707

Replace T bellow with variable type. You will get your work done

priority_queue<T, vector<T>, greater<T> > PQ;

As example for int type variable you can write it like this:

priority_queue<int, vector<int>, greater<int> > Q;

Upvotes: 0

hafiz031
hafiz031

Reputation: 2670

You can just push values multiplying them by -1 so it will be stored in reverse order unlike the actual default order...and multiply the value with -1 again while retrieving data to get it in its actual form.

Upvotes: 1

Mike Seymour
Mike Seymour

Reputation: 254461

  1. priority_queue has template parameters that specify the container type and the comparison to use for ordering. By default, the comparison is less<T>; to get the opposite ordering, use priority_queue<T, vector<T>, greater<T>>.

  2. Insertion into a priority queue takes logarithmic time, so building a queue of N items has complexity O(N logN), the same as building and sorting a vector. But once it's built, insertion into the priority queue is still logarithmic, while insertion into a sorted vector is linear.

Upvotes: 30

kennytm
kennytm

Reputation: 523304

Use the type

priority_queue<T, vector<T>, greater<T> >

Upvotes: 10

pmr
pmr

Reputation: 59811

Use a different comparator as the 3rd template argument of std::priority_queue.

priority_queue is a container adaptor that works on any sequence you define. The performance of insertion is equal to the std::push_heap operation and takes logarithmic time. So the complexity to sorting after all insertions are done isn't equal. If you insert a fixed amount and work the queue afterwards a vector and a single sort could be more efficient.

Upvotes: 1

Related Questions