c++--priority_queue和仿函数

目录

 1.priority_queue

实现：

2.仿函数

priority_queue+仿函数 实现代码

---

1.priority_queue

       优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的，其实就是个堆，默认是大根堆。

       优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。

简单实现：

#pragma once
#include<iostream>
#include<vector>
using namespace std;
namespace ch
{template <class T, class Container = vector<T>>class priority_queue{public:priority_queue(){}void adjust_up(int child) //向上调整算法{size_t parent = (child - 1) / 2;while (child > 0){if (c[parent] < c[child]){swap(c[parent], c[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(int parent) //向下调整算法{size_t child = parent * 2 + 1;while (child < c.size()){if (child + 1 < c.size() && c[child] < c[child + 1]){child++;}if (c[parent] < c[child]){swap(c[parent], c[child]);parent = child;child = parent * 2 + 1;}else{break;}}}template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){c.push(*first);first++;}for (int i = (c.size() - 1 - 1) / 2; i >= 0; i--) //建堆，时间复杂度为O(N){adjust_down(i);}}bool empty() const{return c.empty();}size_t size() const{return c.size();}const T& top(){return c[0];}void push(const T& x){c.push_back(x);adjust_up(c.size() - 1);}void pop(){swap(c[0], c[c.size() - 1]);c.pop_back();adjust_down(0);}private:Container c;};};

引入仿函数实现定义类型时就能决定大小堆 

2.仿函数

    就是定义一个类，类中只有一个重载了()的成员函数，可以有传入参数，需要调用时创建其对象，如：

class Print{void operator()(){cout<<"hehe"<<endl;}};
int main(){Print p;p();}

所以我们写个大于小于逻辑的仿函数，并在创建priority_queue时传入此类即可

priority_queue+仿函数 实现代码

    //小于仿函数template<class T>class myless {public:bool operator()(const T& x,const T& y) {return x < y;}};//大于仿函数template<class T>class mygreater {public:bool operator()(const T& x, const T& y) {return x > y;}};template <class T, class Container = vector<T>, class Compare = myless<T> >class priority_queue{public:priority_queue() = default;template <class InputIterator>priority_queue(InputIterator first, InputIterator last) {while (first != last) {c.push_back(*first);first++;}for (int i = (size()-1-1) / 2; i >= 0; i--) {adjust_down(i);}}bool empty() const {return c.empty();}size_t size() const {return c.size();}const T& top() const {assert(!empty());return c[0];}void adjust_up(size_t child) {while (child > 0) {size_t parent = (child - 1) / 2;if (comp(c[parent] , c[child])) {swap(c[parent], c[child]);}else {break;}child = parent;}}void push(const T& x) {c.push_back(x);adjust_up(c.size()-1);}void adjust_down(size_t parent) {size_t child = parent * 2 + 1;while (child < size()) {if (child + 1 < size() && comp(c[child] , c[child + 1])) {child++;}if (comp(c[parent] , c[child])) {swap(c[child], c[parent]);parent = child;child = child * 2 + 1;}else {break;}}}void pop() {assert(!empty());swap(c[0], c[size() - 1]);c.erase(c.end()-1);adjust_down(0);}private:Container c;Compare comp;};