priority_ queue

#include<queue>
using std::priority_queue;

1. Definition

A little

2. Element access

Only use top(), Go back to team leader （ It can also be said that the top element ）, That is, the element with the highest priority

3. Common function parsing

（1）push()

Time complexity O(logn),n Is the number of elements in the current queue

（2）top()

O(1)

（3）pop()

The first element out of the team ,O(logn)

（4）empty()

true-> empty ,false-> Non empty

（5）size()

4. Priority settings

① Basic data type

priority_queue<typename>;
priority_queue<typename,vector<typename>,less<typename> >;
priority_queue<typename,vector<typename>,greater<typename> >;

1. The first parameter is zero priority_queue Type of internal element

2. The second parameter is the underlying data structure （ Pile up ） The container of , The general default is vector<typename>, change typename that will do

3. The third parameter is less<typename>( The higher the number, the higher the priority ),greater<typename>（ Small numbers have high priority ）, That is, the first element of the team is less Is the maximum , stay greater It's the smallest , The default is less（ and sort Of cmp contrary ）

② Type of structure

1. Overloaded operators inside the structure

struct student
{
    int index;
    int score;
    friend bool operator < (student s1,student s2)
    {
        return s1.score<s2.score;
    }
};
// Call directly with 
priority_queue<student> p1;

Be careful ：

The effect here is similar to sort On the contrary , stay sort This definition will minimize the team leader , But because of priority_queue The default rule is to put the higher priority first , Pay attention to distinguish between

Besides, it can only be overloaded < Symbol , Otherwise it will compile incorrectly , And don't worry about it > And ==, They can be based on < Relationship to transform

2. Overloaded functions outside the structure

struct cmp
{
    bool operator () (student s1,student s2)
    {
        return s1.score<s2.score;
    }
};
// When calling, change the third parameter to the defined structure cmp
priority_queue<student,vector<student>,cmp> p;

Be careful ： If the data in the structure is too large , If a string or array appears , It is recommended to use references to improve efficiency , That is to add const and &

/* Within the structure is defined */
struct student
{
    int score;
    int index;
    friend bool operator < (const student &s1,const student &s2)
    {
        return s1.score<s2.score;
    }
};
/* Definition of structure outside */
struct cmp
{
    bool operator () (const student &s1,const student &s2)
    {
        return s1.score<s2.score;
    }
};

Be careful ： Use top() Pre attention empty()