C++ STL 详解：priority_queue 的使用与模拟实现

C STL 详解priority_queue 的使用与模拟实现文章目录C STL 详解priority_queue 的使用与模拟实现priority_queue 的使用1. priority_queue 是什么2. priority_queue 和普通 queue 的区别3. priority_queue 的定义方式3.1 定义默认大堆3.2 显式指定大堆3.3 显式指定小堆3.4 使用时需要的头文件4. priority_queue 的常用接口5. 大堆使用示例6. 小堆使用示例7. priority_queue 的常见使用场景堆的基础概念1. 什么是堆2. 大堆和小堆3. 堆和数组下标的关系4. priority_queue 为什么底层适合用 vector堆的向上调整算法1. 向上调整解决什么问题2. 大堆的向上调整过程3. 小堆的向上调整过程4. 向上调整代码堆的向下调整算法1. 向下调整解决什么问题2. 大堆的向下调整过程3. 小堆的向下调整过程4. 向下调整代码priority_queue 的模拟实现1. 仿函数 less 和 greater2. priority_queue 接口总览3. push 的实现4. pop 的实现5. top、size、empty 的实现6. 完整模拟实现代码总结priority_queue 的使用1. priority_queue 是什么priority_queue 叫优先级队列它和普通队列不一样普通 queue 是先进先出谁先进来谁先出去priority_queue 看的是优先级优先级高的元素先出去在 STL 中priority_queue 默认使用 vector 作为底层存储容器然后再用堆算法把 vector 里的数据维护成堆结构所以从底层思想上看priority_queue 就是一个堆所有需要用堆的地方都可以先考虑 priority_queue默认情况下priority_queue 是大堆也就是说优先级最高的元素是最大值top 拿到的是当前最大元素2. priority_queue 和普通 queue 的区别普通 queue 的顺序由进入队列的先后决定priority_queue 的顺序由元素大小或比较规则决定比如依次插入3 6 0 2 9 8 1普通 queue 出队顺序是3 6 0 2 9 8 1默认 priority_queue 出队顺序是9 8 6 3 2 1 0原因很简单默认 priority_queue 是大堆每次 top 都是当前最大值3. priority_queue 的定义方式priority_queue 的模板参数一般有三个priority_queueT,Container,Compare三个参数分别表示T 表示存储的元素类型Container 表示底层容器类型Compare 表示比较方式也可以理解成堆的规则3.1 定义默认大堆priority_queueintq;这个写法最常见它等价于默认使用 vector 作为底层容器并且默认构造大堆也就是priority_queueint,vectorint,lessintq;3.2 显式指定大堆priority_queueint,vectorint,lessintq1;less 表示大的元素优先级更高所以 q1 是大堆3.3 显式指定小堆priority_queueint,vectorint,greaterintq2;greater 表示小的元素优先级更高所以 q2 是小堆定义小堆时要包含 functional 头文件#includefunctional3.4 使用时需要的头文件常用头文件如下#includequeue#includevector#includefunctional如果要输出还需要#includeiostream4. priority_queue 的常用接口priority_queue 常用成员函数如下成员函数作用push插入元素并重新调整堆pop删除堆顶元素并重新调整堆top访问堆顶元素size获取有效元素个数empty判断是否为空swap交换两个优先级队列中的数据这些接口可以这样理解push 不是简单尾插尾插后还要保证堆结构正确pop 删除的是堆顶元素也就是优先级最高的元素top 只查看堆顶不删除size 返回当前元素个数empty 判断有没有元素swap 交换两个 priority_queue 的内容注意pop 不会返回被删除的元素如果想拿到将要删除的堆顶元素要先 top再 popintxq.top();q.pop();5. 大堆使用示例#includeiostream#includefunctional#includequeueusingnamespacestd;intmain(){priority_queueintq;q.push(3);q.push(6);q.push(0);q.push(2);q.push(9);q.push(8);q.push(1);while(!q.empty()){coutq.top() ;q.pop();}coutendl;return0;}输出结果9 8 6 3 2 1 0默认是大堆所以每次取出的都是当前最大值6. 小堆使用示例#includeiostream#includefunctional#includequeue#includevectorusingnamespacestd;intmain(){priority_queueint,vectorint,greaterintq;q.push(3);q.push(6);q.push(0);q.push(2);q.push(9);q.push(8);q.push(1);while(!q.empty()){coutq.top() ;q.pop();}coutendl;return0;}输出结果0 1 2 3 6 8 9小堆中堆顶是当前最小值7. priority_queue 的常见使用场景priority_queue 常见使用场景很多尤其是需要动态维护最大值或最小值的时候可以重点记这些求一组数据中的前 K 大求一组数据中的前 K 小堆排序相关场景Dijkstra 最短路算法Huffman 编码任务调度优先级高的任务先处理合并多个有序序列数据流中的中位数问题普通排序适合一次性处理全部数据priority_queue 更适合边插入边取最值的场景堆的基础概念1. 什么是堆堆是一种特殊的完全二叉树完全二叉树的特点是除了最后一层以外前面的每一层都是满的最后一层从左到右连续排列堆还要满足父子结点之间的大小关系如果每个父结点都大于或等于它的孩子这就是大堆如果每个父结点都小于或等于它的孩子这就是小堆priority_queue 底层使用的就是堆结构2. 大堆和小堆大堆的特点堆顶元素最大每个父结点都大于或等于孩子结点每次取 top拿到的是当前最大值小堆的特点堆顶元素最小每个父结点都小于或等于孩子结点每次取 top拿到的是当前最小值注意堆只保证父子之间的大小关系不保证整体有序比如大堆能保证堆顶最大但不能保证数组从前到后完全降序3. 堆和数组下标的关系堆虽然逻辑上是一棵完全二叉树但实际存储时一般放在数组或 vector 中假设某个结点下标是 child它的父结点下标是parent (child - 1) / 2假设某个结点下标是 parent它的左孩子下标是left parent * 2 1它的右孩子下标是right parent * 2 2比如数组下标结构是0 / \ 1 2 / \ / \ 3 4 5 6这种下标关系就是堆能用 vector 存储的原因4. priority_queue 为什么底层适合用 vectorpriority_queue 的底层默认用 vector原因很直接堆本质上是完全二叉树完全二叉树可以用数组下标关系表示vector 支持随机访问vector 尾插效率高push 时新元素先放到尾部再向上调整pop 时把堆顶和尾部交换再删除尾部最后向下调整所以 vector 很适合堆这种结构堆不需要频繁在中间插入删除只需要尾部插入、尾部删除和按下标访问父子结点这些操作正好都是 vector 擅长的堆的向上调整算法1. 向上调整解决什么问题向上调整一般用在插入新元素之后堆中原来的数据已经满足堆结构新元素被插入到数组尾部这个新元素可能比它的父结点更大或者在小堆中比父结点更小这时只需要让新元素一路和父结点比较必要时交换直到堆重新合法这个过程就叫向上调整2. 大堆的向上调整过程假设要维护大堆插入新元素后新元素下标是 child父结点下标是parent (child - 1) / 2如果 child 位置的值大于 parent 位置的值就交换它们交换之后child 更新为 parent继续向上比较直到child 已经到根结点或者 child 位置的值不再大于 parent 位置的值举个例子原来有一个大堆9 6 8 2 3 0 1插入 10 后先放到尾部9 6 8 2 3 0 1 1010 和父结点 2 比10 更大交换9 6 8 10 3 0 1 210 和父结点 6 比10 更大交换9 10 8 6 3 0 1 210 和父结点 9 比10 更大交换10 9 8 6 3 0 1 2调整结束堆顶变成 103. 小堆的向上调整过程小堆和大堆类似只是比较规则反过来小堆中如果 child 位置的值小于 parent 位置的值就交换插入的新元素如果很小就会一路往上走直到找到合适位置4. 向上调整代码下面这个版本通过 Compare 控制大堆和小堆Compare 是 less 时维护大堆Compare 是 greater 时维护小堆templateclassT,classContainer,classComparevoidAdjustUp(Containercon,size_t child){Compare com;while(child0){size_t parent(child-1)/2;// 如果父结点优先级低于孩子就交换if(com(con[parent],con[child])){std::swap(con[parent],con[child]);childparent;}else{break;}}}为什么 less 可以维护大堆因为 less()(parent, child) 为 true 时说明 parent child大堆里父结点要更大所以 parent 和 child 应该交换为什么 greater 可以维护小堆因为 greater()(parent, child) 为 true 时说明 parent child小堆里父结点要更小所以 parent 和 child 应该交换堆的向下调整算法1. 向下调整解决什么问题向下调整一般用在删除堆顶之后priority_queue 的 pop 删除的是堆顶元素但是堆顶不能直接删除因为堆顶在数组下标 0 的位置直接删除会破坏数组结构通常做法是交换堆顶元素和最后一个元素删除最后一个元素从堆顶开始向下调整删除后根结点位置可能不满足堆规则所以要让它和孩子中优先级更高的那个比较必要时交换2. 大堆的向下调整过程大堆中父结点应该大于或等于孩子结点如果父结点比孩子中较大的那个还小就交换交换后继续向下调整直到没有孩子或者父结点已经大于等于两个孩子比如大堆10 9 8 6 3 0 1 2要删除堆顶 10先把堆顶和最后一个元素交换2 9 8 6 3 0 1 10删除尾部 102 9 8 6 3 0 1从 2 开始向下调整左右孩子是 9 和 8选择更大的 9 交换9 2 8 6 3 0 12 的孩子是 6 和 3选择更大的 6 交换9 6 8 2 3 0 1调整结束3. 小堆的向下调整过程小堆中父结点应该小于或等于孩子结点如果父结点比孩子中较小的那个还大就交换每次要优先选择两个孩子中更小的那个这样才能保证小堆的堆顶一直是最小值4. 向下调整代码下面这个版本同样通过 Compare 控制大堆和小堆templateclassT,classContainer,classComparevoidAdjustDown(Containercon,size_t parent){Compare com;size_t sizecon.size();size_t childparent*21;while(childsize){// 如果右孩子存在并且右孩子优先级比左孩子高就选右孩子if(child1sizecom(con[child],con[child1])){child;}// 如果孩子优先级比父结点高就交换if(com(con[parent],con[child])){std::swap(con[parent],con[child]);parentchild;childparent*21;}else{break;}}}这里最关键的是选孩子大堆里要选更大的孩子小堆里要选更小的孩子这个选择也通过 Compare 来完成priority_queue 的模拟实现1. 仿函数 less 和 greater标准库里有 less 和 greater为了更好理解 Compare 的作用可以自己简单写一个templateclassTstructLess{booloperator()(constTx,constTy)const{returnxy;}};templateclassTstructGreater{booloperator()(constTx,constTy)const{returnxy;}};Less 表示当 x y 时返回 true如果在堆调整中发现父结点和孩子满足 Less也就是父结点比孩子小就交换最终得到大堆Greater 表示当 x y 时返回 true如果在堆调整中发现父结点比孩子大就交换最终得到小堆2. priority_queue 接口总览模拟实现一个 priority_queue主要接口有pushpoptopsizeemptyswap底层需要一个容器保存数据默认用 vector还需要一个比较器 Compare默认使用 Less也就是默认构造大堆3. push 的实现push 的步骤先把新元素插入到底层容器尾部新元素此时在最后一个位置对最后一个位置做向上调整调整完成后堆结构恢复正确核心代码voidpush(constTx){_con.push_back(x);AdjustUp(_con.size()-1);}4. pop 的实现pop 的步骤交换堆顶元素和尾部元素删除尾部元素从堆顶位置开始向下调整调整完成后新的堆顶就是当前优先级最高的元素核心代码voidpop(){std::swap(_con[0],_con[_con.size()-1]);_con.pop_back();AdjustDown(0);}注意pop 前要保证队列不为空如果容器为空访问 _con[0] 就是非法访问5. top、size、empty 的实现top 直接返回下标 0 位置的元素因为堆顶永远放在数组的第一个位置constTtop()const{return_con[0];}size 直接调用底层容器的 sizesize_tsize()const{return_con.size();}empty 直接调用底层容器的 emptyboolempty()const{return_con.empty();}6. 完整模拟实现代码#pragmaonce#includevector#includecassert#includealgorithmnamespacecl{templateclassTstructLess{booloperator()(constTx,constTy)const{returnxy;}};templateclassTstructGreater{booloperator()(constTx,constTy)const{returnxy;}};templateclassT,classContainerstd::vectorT,classCompareLessTclasspriority_queue{public:priority_queue(){}templateclassInputIteratorpriority_queue(InputIterator first,InputIterator last){while(first!last){_con.push_back(*first);first;}// 从最后一个非叶子结点开始向下调整建堆效率更高for(intistatic_castint((_con.size()-2)/2);i0;--i){AdjustDown(i);}}voidpush(constTx){_con.push_back(x);AdjustUp(_con.size()-1);}voidpop(){assert(!_con.empty());std::swap(_con[0],_con[_con.size()-1]);_con.pop_back();if(!_con.empty()){AdjustDown(0);}}constTtop()const{assert(!_con.empty());return_con[0];}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}voidswap(priority_queueT,Container,Compareq){_con.swap(q._con);}private:voidAdjustUp(size_t child){Compare com;while(child0){size_t parent(child-1)/2;// 如果孩子优先级高于父结点就交换if(com(_con[parent],_con[child])){std::swap(_con[parent],_con[child]);childparent;}else{break;}}}voidAdjustDown(size_t parent){Compare com;size_t childparent*21;while(child_con.size()){// 选出左右孩子中优先级更高的那个if(child1_con.size()com(_con[child],_con[child1])){child;}// 如果孩子优先级高于父结点就向下交换if(com(_con[parent],_con[child])){std::swap(_con[parent],_con[child]);parentchild;childparent*21;}else{break;}}}private:Container _con;};}建堆构造函数里有一个点要注意如果有一批数据已经在容器中想把它们变成堆可以从最后一个非叶子结点开始向下调整最后一个非叶子结点下标是(_con.size() - 2) / 2从这个位置一直调整到 0就能完成建堆这样建堆的效率比一个个 push 更好总结priority_queue 的重点可以这么记priority_queue 是容器适配器它底层默认使用 vector 存数据它通过堆算法维护优先级默认情况下是大堆top 返回堆顶元素push 插入元素后要向上调整pop 删除堆顶后要向下调整less 对应大堆greater 对应小堆堆的父子下标关系必须熟悉向上调整主要用在插入新元素之后向下调整主要用在删除堆顶元素之后模拟实现 priority_queue 的关键不是接口本身而是理解底层堆结构怎么维护只要把向上调整和向下调整搞清楚priority_queue 的 push、pop、top 基本就都顺了