C++ priority

一、模板参数

优先队列有三个参数，其声明形式为

priority_queue< type, container, function >

这三个参数，后面两个在一些情况下可以省略，第一个不可以。

其中：

type：数据类型；container：实现优先队列的底层容器；function：元素之间的比较方式 

 二、int类型的数据

 1. 第三参数，有：

less<int> //表示大根堆 greater<int> //表示小根堆 //在默认情况下使用的是less<int>

2. 默认情况下priority_queue的使用

vector<int> nums = { 54,1,5,4,8,6,29,49,6,194,9,26 }; 默认情况选下，不需要后两个参数 priority_queue<int> prque; for (int i = 0; i < nums.size(); i++) { prque.push(nums[i]); } while (!prque.empty()) { cout << prque.top() << endl; prque.pop(); }

3. 小根堆priority_queue的使用

vector<int> nums = { 54,1,5,4,8,6,29,49,6,194,9,26 }; 非默认情况选下，需要加上后两个参数 priority_queue<int,vector<int>, greater<int>> prque; for (int i = 0; i < nums.size(); i++) { prque.push(nums[i]); } while (!prque.empty()) { cout << prque.top() << endl; prque.pop(); }

三、自定义类型的比较

 1. 自定义的类型

struct node{ int x; int y; };

2. 重载 < 运算符，实现小根堆与大根堆

注意：重载 < 运算符，同样可以不用写后两个参数

函数中 使用的是<：表示大根堆，>：表示小根堆 bool operator< (node a, node b) { //return a.y < b.y; //大根堆 //return a.y > b.y; //小根堆 } priority_queue<node> prque; node pp; for (int i = 0; i < nums.size(); i++) { pp.x = i; pp.y = nums[i]; prque.push(pp); } while (!prque.empty()) { cout << prque.top().y << endl; prque.pop(); }

 

3. 重写仿函数实现大根堆与小根堆

注意：重写仿函数，必须加上后面两个参数

函数中 使用的是<：表示大根堆，>：表示小根堆 struct cmp //重写仿函数 { bool operator() (node a, node b) { //return a.y < b.y; //大根堆 //return a.y > b.y; //小根堆 } }; priority_queue<node,vector<node>,cmp> prque; node pp; for (int i = 0; i < nums.size(); i++) { pp.x = i; pp.y = nums[i]; prque.push(pp); } while (!prque.empty()) { cout << prque.top().y << endl; prque.pop(); }