Have Geek Brain

Stl queue priority based on lower value

I have a problem with the stl priority queue. I want to have a priority queue in ascending order that is decremented by default. Is there a way to do this in a priority queue.

And what is the complexity of constructing a stl priority queue.If I am using quicksort on an array which takes O (nlgn), its complexity is similar to using a priority queue ???

Plz someone ans.Advanced thanx.

+1


a source to share


6 answers


Use another comparator as the third template argument std::priority_queue

.



priority_queue is a container adapter that works in whatever order you define. Insertion performance is equal to the operation std::push_heap

and takes logarithmic time. Thus, the complexity of the sort after all insertions is not equal. If you insert a fixed amount and then work with a queue vector

, one sort

might be more efficient.

+1


a source


  • priority_queue

    have template parameters that define the type of container and the comparison to use for the order. The default is comparison less<T>

    ; to get the opposite order, use priority_queue<T, vector<T>, greater<T>>

    .

  • Inserting into a priority queue takes logarithmic time, so building a queue of elements N

    has O(N logN)

    the same complexity as creating and sorting a vector. But once created, insertion into the priority queue is still logarithmic, and insertion into a sorted vector is linear.



+27


a source


Use type

priority_queue<T, vector<T>, greater<T> >
+8


a source


You can just move the values ​​by multiplying them by -1 so that they are stored in the opposite order, as opposed to the actual default order ... and multiply the value with -1 again when you get the data to get it in its actual form.

+1


a source


Replace the T below with a variable type. You will do your job

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

As an example for a variable of type int, you can write it like this:

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


a source


You can use a comparator class / structure to achieve the same in a 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;
0


a source






More articles:


All Articles