STL 最大堆、最小堆的应用 以你之姓@ 2022-06-08 05:53 183阅读 0赞 ## 1.priority\_queue ## priority\_queue默认是最大堆，要用最小堆需要比较函数`greater<int>` priority_queue<int, vector<int>, less<int>> maxHeap; priority_queue<int, vector<int>, greater<int>> minHeap; 也可以自定义比较函数 struct cmp { bool operator()(const int &a, const int &b) { return a > b; } }; priority_queue<int, vector<int>, cmp> minHeap; 如果不是内置类型，也可以 struct cmp { bool operator()(const Node&a, const Node&b) { return a.val > b.val; } }; ## 2. STL 堆操作 ## 头文件是`#include <algorithm>` 一般用到这四个：make\_heap()、pop\_heap()、push\_heap()、sort\_heap(); **（1）make\_heap()**构造堆 void make\_heap(first\_pointer,end\_pointer,compare\_function); 默认比较函数是(<)，即最大堆。 函数的作用是将\[begin,end)内的元素处理成堆的结构 **（2）push\_heap()**添加元素到堆 void push\_heap(first\_pointer,end\_pointer,compare\_function); 新添加一个元素在末尾，然后重新调整堆序。该算法必须是在一个已经满足堆序的条件下。 先在vector的末尾添加元素，再调用push\_heap **（3）pop\_heap()**从堆中移出元素 void pop\_heap(first\_pointer,end\_pointer,compare\_function); 把堆顶元素取出来，放到了数组或者是vector的末尾。 要取走，则可以使用底部容器（vector）提供的pop\_back()函数。 先调用pop\_heap再从vector中pop\_back元素 **（4）sort\_heap()**对整个堆排序 排序之后的元素就不再是一个合法的堆了。 用法： void testHeap() { vector<int> data{ 3,1,2,7,5 }; //构造堆，最大堆 make_heap(data.begin(), data.end(), less<int>()); //pop堆顶元素，最大的元素 pop_heap(data.begin(), data.end(), less<int>()); cout << data.back() << endl;//输出7 data.pop_back(); //往堆中添加元素 data.push_back(4); push_heap(data.begin(), data.end(), less<int>());//调整堆 //排序 sort_heap(data.begin(), data.end(), less<int>()); for (int x : data) cout << x << " "; cout << endl;//输出 1，2，3，4，5 }
还没有评论，来说两句吧...