STL priority_queue 常见用法详解

《算法笔记》学习笔记

priority_queue 常见用法详解

//priority_queue又称优先队列，其底层时用堆来实现的。

//在优先队列中，队首元素一定是当前队列中优先级最高的那一个。

桃子(优先级 3)

梨子(优先级 4)

苹果(优先级 1)

//那么出队顺序是：梨子(4) -> 桃子(3) -> 苹果(1)

//可以在任何时候往优先队列里面加入(push)元素，而优先队列底层的数据结构对(heap)

//会随时调整结构，使得每次的队首元素都是优先级最大的

1. priority_queue 的定义

//定义

priority_queue< typename > name;

2. priority_queue容器内元素访问

//只能通过top()函数来访问队首元素（也称堆顶元素)，也就是优先级最高的元素

#include <stdio.h>

#include <queue>

using namespace std;

int main() {

    priority_queue<int> q;

    q.push(3);

    q.push(4);

    q.push(1);

    printf("%d\n", q.top());

    return 0;

}

3. priority_queue常用函数实例解析

(1) push()

//push(x)将令x入队，时间复杂度为O(logN),其中N为当前优先队列中的元素个数。

(2) top()

//top()可以获得队首元素，时间复杂度为O(1)

//使用top()函数之前，必须用empty()判断优先队列是否为空

(3) pop()

//pop()令队首元素出队，时间复杂度为O（logN)，其中N为当前优先队列中的元素个数

#include <stdio.h>

#include <queue>

using namespace std;

int main() {

    priority_queue<int> q;

    q.push(3);

    q.push(4);

    q.push(5);

    q.push(1);

    printf("%d\n", q.top());

    q.pop();

    printf("%d\n", q.top());

    return 0;

}

(4) empty()

//empty()检测优先队列是否为空，返回true则空，返回false则非空。时间复杂度为O(1)

#include <stdio.h>

#include <queue>

using namespace std;

int main() {

    priority_queue<int> q;

    if(q.empty() == true) { //一开始优先队列内没有元素，所以是空

        printf("Empty\n");

    } else {

        printf("Not Empty\n");

    }

    q.push(1);

    if(q.empty() == true) { //在加入"1"后，优先队列非空

        printf("Empty\n");

    } else {

        printf("Not Empty\n");

    }

    return 0;

}

(5) size()

//size()返回优先队列内元素的个数，时间复杂度为O(1)

#include <stdio.h>

#include <queue>

using namespace std;

int main() {

    priority_queue std;

    q.push(3);

    q.push(4);

    q.push(1);

    printf("%d\n", q.size());   //优先队列中有三个元素

    return 0;

}

4.priority_queue内元素优先级的设置

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

//基本数据类型就是int型, double型， char型等可以直接使用的数据类型

//优先队列对他们的优先级设置一般是数字大的优先级越高

//因此队首元素就是优先队列内元素最大的那个（如果是char型,则是字典序最大的）

//下面两种优先队列的定义是等价的（以int型为例，注意最后两个>之间有一个空格）：

priority_queue<int> q;

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

//第二种定义方式的尖括号内多出两个参数：vector<int>, less<int>

//其中vector<int>填写的是来承载底层数据结构堆(heap)的容器

//如果第一个参数是double型或char型，则此处只需要填写vector<double>或vector<char

//第三个参数less<int>则是对第一个参数的比较类。

//less<int>表示数字大的优先级越大，而greater<int>表示数字小优先级越大

//优先队列总数把最小的元素放在队首，定义

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

//示例

#include <stdio.h>

#include <queue>

using namespace std;

int main() {

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

    q.push(3);

    q.push(4);

    q.push(1);

    printf("%d\n", q.top());

    return 0;

}

(2) 结构体的优先级设置

//对水果的名称和价格建立结构体

struct fruit {

    string name;

    int price;

};

//现在希望水果的价格高的为优先级高，就需要重载(overload)小于"<"。

//重载是指对已有的运算符进行重新定义，也就是说，可以改变小于号的功能。

struct fruit {

    string name;

    int price;

    friend bool oprator < (fruit f1, fruit f2) {

        return f1.price < f2.price;

    }

};

//fruit结构体种增加了一个函数，其中"friend"为友元。

//想要以价格低的水果为优先级高，只需要把return中的小于号改为大于号即可。

struct fruit {

    string name;

    int price;

    friend bool operator < (fruit f1, fruit f2) {

        return f1.price > f2.price;

    }

};

//示例：

#include <iostream>

#include <string>

#include <queuen>

using namespace std;

struct fruit {

    string name;

    int price;

    friend bool operator < (fruit f1, fruit f2) {

        return f1.price > f2.price;

    }

}f1, f2, f3;

int main() {

    priority_queue<fruit> q;

    f1.name = "桃子";

    f1.price = 3;

    f2.name = "梨子";

    f2.price = 4;

    f3.name = "苹果";

    f3.price = 1;

    q.push(f1);

    q.push(f2);

    q.push(f3);

    cout << q.top().name << " " << q.top().price << endl;

    return 0;

}

//优先队列的这个函数与sort中的cmp函数的效果是相反的

//上面的函数有没有办法同sort中的cmp函数那样卸载结构体外面

//方法：把friend去掉，把小于号改成一对小括号，然后把重载的函数写在结构体外面

//同时将其用struct包装起来

struct cmp {

    bool operator () (fruit f1,fruit f2) {

        return f1.price > f2.price;

    }

}

//这种情况需要使用第二种定义方法来定义优先队列

priority_queue<fruit, vector<fruit>, cmp> q;

//把greater<>部分换成cmp

#include <iostream>

#include <string>

#include <queue>

using namespace std;

struct fruit {

    string name;

    int price;

} f1, f2, f3;

struct cmp {

    bool operator () (fruit f1, fruit f2) {

        return f1.price > f2.price;

    }

};

int main() {

    prority_queue<fruit, vector<fruit>, cmp> q;

    f1.name = "桃子";

    f1.price = 3;

    f2.name = "梨子";

    f2.price = 4;

    f3.name = "苹果";

    f3.price = 1;

    q.push(f1);

    q.push(f2);

    q.push(f3);

    cout << q.top().name << " " << q.top().price << endl;

    return 0;

}

//即使是基本数据类型或者其他STL容器(例如set),也可以通过同样的方式来定义优先级

//建议使用引用来提高效率，在比较类的参数种需要加上"const" 和"&"

friend bool operator < (const fruit &f1, const fruit &f2) {

    return f1.price > f2.price;

}

bool operator () (const fruit &f1, const fruit &f2) {

    return f1.price > f2.price;

}

5. priority_queueu的常见用途

可以解决一些贪心问题
也可以对Dijkstra算法进行优化（因为优先队列的本质是堆）

巴特西

STL priority_queue 常见用法详解

priority_queue 常见用法详解

1. priority_queue 的定义

2. priority_queue容器内元素访问

3. priority_queue常用函数实例解析

4.priority_queue内元素优先级的设置

5. priority_queueu的常见用途

最新文章

热门文章