当前位置:首页 » 《随便一记》 » 正文

C++ —— 优先级队列(priority queue)的模拟实现

26 人参与  2024年12月24日 12:01  分类 : 《随便一记》  评论

点击全文阅读


目录

杂谈

vector和list的区别

1. 优先级队列的定义

2. 优先级队列的模拟实现

3. 仿函数


链接:

priority_queue - C++ Reference (cplusplus.com)icon-default.png?t=O83Ahttps://legacy.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue


杂谈

vector和list的区别

在这种情况下诞生了一个缝合怪:deque

 

但是依旧有缺陷 


1. 优先级队列的定义

队列是一种先进先出的数据类型。元素的入队都只能从队尾进入,出队时从队列头部出去

*

优先级队列不能先进先出,更像是数据类型中的“堆”,也就是数组

优先级队列每次出队的元素是队列中优先级最高的那个元素,默认大的值优先级高,如果想要小的值优先级高可以使用仿函数,而不是队首的元素,也就是每次出队,都是将当前队列中最大的那个元素出队


2. 优先级队列的模拟实现

假设父节点在数组中的下标为i,那么:

                                                        1.左孩子在数组中的下标为:2*i+1 

                                                        2.右孩子在数组中的下标为:2*i+2

假设孩子在数组中的下标为i,那么:

                                                        父在数组中的下标为:(i - 1)/ 2

在这里不区分左孩子和右孩子,因为除以会向下取整

#pragma once//优先级队列:默认大的值优先级高,如果想要小的值优先级高可以使用仿函数//底层是堆namespace bit{template<class T, class Container = vector<T>>class priority_queue{public://堆的向上调整void AdjustUp(size_t child){//孩子/2找到父节点int parent = (child - 1) / 2;//孩子大于0就进入/继续while (child > 0){//如果孩子小于父亲if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}//向下调整void AdjustDown(size_t parent){// 先假设左孩子小int child = parent * 2 + 1;// child >= n说明孩子不存在,调整到叶子了while (child < 0){//找到大的子结点 if (child + 1 < _con.size() && _con[child] < _con[child + 1]){child++;}//if (_con[child] > _con[parent]) 大堆//孩子小于父亲if (_con[child] < _con[parent])//小堆{swap(_con[child], _con[parent]);parent = child;//继续算左孩子child = parent * 2 + 1;}else{break;}}}void push(const T & x){//插入数据之前已经是一个堆了,那么数据就要_con.push_back(x);//从堆底向上调整AdjustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top(){return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};}


3. 仿函数

仿函数的本质是一个类,使用到了仿函数来重载 operator(),以达到改变大/小堆的功能,他的对象可以像函数一样使用

// 仿函数:本质是一个类,这个类重载operator(),他的对象可以像函数一样使用template<class T>class Less{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>class Greater{public:bool operator()(const T& x, const T& y){return x > y;}};
#pragma once//优先级队列:默认大的值优先级高,如果想要小的值优先级高可以使用仿函数//底层是堆namespace bit{template<class T, class Container = vector<T>>class priority_queue{public://堆的向上调整void AdjustUp(size_t child){Compare com;//孩子/2找到父节点int parent = (child - 1) / 2;//孩子大于0就进入/继续while (child > 0){//如果孩子小于父亲//if (_con[parent] < _con[child])//将大的值移向堆顶,建大堆if (com(_con[child], _con[parent])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}//向下调整void AdjustDown(size_t parent){Compare com;// 先假设左孩子小int child = parent * 2 + 1;// child >= n说明孩子不存在,调整到叶子了while (child < 0){//找到大的子结点 //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[child] < _con[parent])//小堆if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;//继续算左孩子child = parent * 2 + 1;}else{break;}}}void push(const T & x){//插入数据之前已经是一个堆了,那么数据就要_con.push_back(x);//从堆底向上调整AdjustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top(){return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};}

感谢观看~


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/206074.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1