C++ priority

    科技2022-07-17  111

    一、模板参数

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

    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(); }

     

    Processed: 0.009, SQL: 8