priority_queue

• 底层是用堆实现的
• 队首元素一定是优先级最高的那个
• 可以在任何时候往优先级队列中加入元素，而优先级队列底层的数据结构是堆会随时调增结构，使得每次的队首元素都是优先级最大的

1. how to use?

#include<queue>
using namespace std;

2. priority_queue的定义

• priority_queue<typename> name;

3. 元素访问

• 只能通过top()来访问堆顶元素

4. 常用函数

1. push(x): O(logN)
2. top(): O(1)
3. pop(): O(logN)
4. empty(): O(1)
5. size(): O(1)

5. 元素优先级的设置

1. 基本数据类型的优先级设置

queue<int> q;
queue<int, vector<int>, less<int>>;

• 上面两种写法是等价的
• 数字大的优先级高
• vector<int>: 承载底层数据结构堆的容器，typename得和queue的元素类型相同
• less<int>: 对第一个参数的比较类，它表示数字大的优先级高，而greater<int>表示数字小的优先级高
• 如果想用小根堆：priority<int, vector<int>, greater<int> > p

2. 结构体的优先级设置

struct fruit{
    string name;
    int price;
}

• 希望按水果价格高的为优先级高，就需要重载小于号<

struct fruit{
    string name;
    int price;
    friend bool operator < (fruit f1, fruit f2) {
        return f1.price < f2.price;
    }
}

• 有没有办法不写成友元的形式，写在结构体的外边
  • 把friend去掉
  • 把小于号改成一堆小括号
  • 把重载的函数写在结构体外面，将其用struct包装起来

struct cmp {
    bool operator(fruit f1, fruit f2) {
        return f1.price < f2.price;
    }
}
// 不同的定义方式
priority_queue<fruit, vector<fruit>, cmp> q;

• 如果要以价格低的水果为优先级高，那么只需要把return中的小于号改为大于号。
• 注意：重载大于号会编译错误
• 优先级队列的这个函数与sort中的cmp函数的效果是相反的，
  • 在cmp中，如果是return f1.price > f2.price，则是降序的。而优先级队列则是把最小的放在队首。
• 如果结构体内数据比较庞大，建议使用引用来提高效率，此时比较类的参数需要加上const和&

struct cmp {
    bool operator(const fruit& f1, const fruit& f2) {
        return f1.price < f2.price;
    }
}

6. 常见用途

1. 解决贪心的问题
2. 对Dijkstra算法进行优化（因为优先级队列的本质是堆）
3. 使用top()前，必须使用empty()判断优先级队列是否为空，否则可能因为队空而出现错误

7. 相关习题

• 任务调度

  • 题解

• 我的答案

#include<iostream>
#include<string>
#include<map>
#include<queue>
using namespace std;
int N;

struct dispatch{
    string name;
    int level;
    friend bool operator <(dispatch d1, dispatch d2) {
        if(d1.level == d2.level) return d1.name > d2.name;
        else return d1.level < d2.level;
    }
} dispatches[100001];

int main() {
    scanf("%d", &N);
    int cnt = 0;
    map<string, int> tasks;
    priority_queue<dispatch> q;

    
    for(int i = 0; i < N; i++) {
        string sentence;
        getline(cin, sentence);
        string word;
        int level = -1;
        for(int j = 0; j < sentence.length(); j++) {
            if(sentence[j] == '(' || sentence[j] == ')' || sentence[j] == ',') {
                // the task must be done in advance
                if(sentence[j] == '(') {
                    if(tasks[word] == 0) {
                        dispatches[cnt].name = word;
                        dispatches[cnt].level = level;
                        tasks[word] = level;
                        q.push(dispatches[cnt++]);
                    }
                    else {
                        // update the value of level
                        level = tasks[word];
                    }
                }
                else {
                    if(word == "NULL") {
                        break;
                    }
                    else {
                        if(tasks[word] == 0) {
                            dispatches[cnt].name = word;
                            dispatches[cnt].level = level-1;
                            tasks[word] = level-1;
                            q.push(dispatches[cnt++]);
                        }
                        else {
                            continue;
                        }
                    }
                }
                word = "";
            }
            else {
                word += sentence[j];
            }
        }
    }
    while(!q.empty()) {
        cout << q.top().name<<" ";
        q.pop();
    }
    return 0;
}