当前位置：首页 > news >正文

优先级队列的模拟实现（仿函数）

news 2025/9/15 9:14:32

目录：

1.priority_queue接口的实现（先建大堆）

1.push 加向上调整的实现

2.pop

3.迭代器区间的构造

2.仿函数

3.仿函数优化我们的优先级队列

------------------------------------------------------------------------------------------------------------------------------

1.priority_queue接口的实现

1.push 加向上调整的实现

优先级队列的底层类似于一个数组的东西

我们需要实现向上调整

2.pop

向下调整

3.迭代器区间的构造

那么写了一个迭代器期区间的构造，我们就需要在实现一个的构造函数

我们写了一个显示构造函数，编译器就不会在默认生成构造函数

调用它自己的默认拷贝构造

namespace cdc
{template<class T,class Container =vector<T>>class priority_queue{public:priority_queue(){}template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);}for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){Adjust_down(i);}}void Adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child>0){if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);Adjust_up(_con.size()-1);}void Adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child<_con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1]){child++;}if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);parent = child;child = parent *2 +1;}else{break;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();//进行向下调整Adjust_down(0);}const T& top() const {return _con[0];}bool empty() const {return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};}

2.仿函数

可是我们上面的队列只能排降序（建大堆），这样子就写死了，那么我们怎么才能写灵活呢，能够简单的控制建大堆还是建小堆

仿函数 /函数对象 --类，这个类重载operator（）

它的less的类对象可以像函数一样去使用

namespace cdc
{template<class T>class less{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>class greater{public:bool opeartor()(const T& x, const T& y){return x > y;}};
}int main()
{cdc::less<int> Isfunc;cout << Isfunc(1, 2) << endl;return 0;
}

less 、greater 类库里都有实现的

3.仿函数优化我们的优先级队列

我们直接用库里的 less 和 greater ，控制我们的比较

namespace cdc
{template<class T,class Container =vector<T>,class Compare=std::less<T>>class priority_queue{public:priority_queue(){}template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);}for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){Adjust_down(i);}}void Adjust_up(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child>0){//if (_con[child] > _con[parent])//if (_con[parent]<_con[child])if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);Adjust_up(_con.size()-1);}void Adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child<_con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child] , _con[child + 1])){child++;}//if (_con[child] > _con[parent])//if (_con[parent] < _con[child])if (com(_con[parent] , _con[child])){std::swap(_con[child], _con[parent]);parent = child;child = parent *2 +1;}else{break;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();//进行向下调整Adjust_down(0);}const T& top() const {return _con[0];}bool empty() const {return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};}

我们less默认是大堆

greater是小堆

查看全文

http://www.lryc.cn/news/59123.html