一、基础概念priority_queue叫优先队列底层不是队列是堆大顶堆 / 小顶堆属于容器适配器。适配器不自己实现底层存储复用别的容器vector/deque做底层只在外层封装堆操作。 队列先进先出优先队列优先级最高的元素先出和入队顺序无关。头文件#include queue// STL原型 template class T, class Container vectorT, class Compare lessT class priority_queue;三个模板参数T存储元素类型Container底层容器默认vectorT要求支持[]、push_back、pop_backCompare仿函数二元谓词默认lessT决定优先级规则⚠️ 最重要规则和你手写仿函数完全一致comp(a,b)返回 true →a 的优先级低于 bb 要排在 a 前面大顶堆要求父节点应该大于等于子节点当子节点 父节点的时候才交换。默认传小于Less仿函数大的优先级高传大于Greater仿函数小的优先级高二、默认大顶堆原理priority_queueint默认priority_queueint, vectorint, lessintlessintcomp(a,b)a bcomp(parent, child)→parent child返回 true父优先级 子子上浮堆顶是最大元素→大顶堆小顶堆写法priority_queueint, vectorint, greaterint minHeap;greaterintcomp(a,b)a b堆顶是最小元素。面试高频坑less→ 大顶堆greater→ 小顶堆很多人记反三、底层堆原理二叉堆完全二叉树数组存储用数组映射完全二叉树父节点下标parent左孩子2*parent 1右孩子2*parent 2子节点找父(child - 1)/2整数除法向下取整堆的两个核心操作向上调整 adjust_up插入 push新元素插在数组末尾不断和父节点比较如果子优先级更高交换父子直到不满足条件 / 到根。对应 pushpush_backadjust_up(最后一个下标)向下调整 adjust_down删除 pop堆顶和末尾元素交换pop_back删掉堆顶新堆顶向下不断和优先级更高的孩子交换直到满足堆性质。对应 pop首尾 swap pop_back adjust_down (0)建堆迭代器区间构造从最后一个非叶子节点开始向前依次向下调整。 最后一个非叶子节点下标(n-2)/2时间复杂度O (n)不是 O (nlogn)插入单个元素O (logn)删除堆顶O (logn)建堆O (n)四、priority_queue 常用接口接口作用注意事项push(x)插入元素自动调整堆底层 push_back 向上调整pop()删除堆顶优先级最高元素不返回堆顶元素空队列调用 UBtop()获取堆顶元素的引用空队列调用 UBconst 引用empty()判空boolsize()返回元素个数size_tqueue 的 front () 返回队首并 pop 分开priority_queuepop()只删不取top()只取不删。#include queue int main() { priority_queueint max_pq; //大顶堆 max_pq.push(1); max_pq.push(9); max_pq.push(5); while(!max_pq.empty()) { cout max_pq.top() ; max_pq.pop(); } //输出9 5 1 return 0; }五、仿函数 Compare 深度理解Compare comp是二元谓词仿函数comp(a,b)返回 boolcomp(a,b) true a 优先级低于 bb 应该放在 a 上方堆中 b 优先级更高// lessT bool operator()(const T a,const T b) { return a b; }comp(p,c)→p c→ true父 p 优先级低于子 c → 交换上浮大顶堆。// greaterT bool operator()(const T a,const T b) { return a b; }comp(p,c)→pc→ true父 p 优先级低于子 c → 交换上浮小顶堆。记忆口诀less是拿比较大顶堆greater拿比较小顶堆六、容器适配器一、什么是容器适配器容器适配器Container Adapter本身不是独立容器它是对已有容器的封装。适配器不自己开辟内存、不实现底层存储复用底层容器的已有接口对外只暴露一套新的、简化的接口改变容器的行为。一句话理解适配器 套壳包装。底层容器负责存数据适配器只提供特定访问规则。一句话理解适配器 套壳包装。底层容器负责存数据适配器只提供特定访问规则。STL 一共 3 个容器适配器stack栈后进先出 LIFOqueue队列先进先出 FIFOpriority_queue优先队列优先级最高元素先出堆适配器默认底层容器底层容器要求stackdequeT支持push_back/pop_back/back()queuedequeT支持push_back/pop_front/back()/front()priority_queuevectorT支持随机访问[]、push_back、pop_back堆算法需要随机下标访问适配器只是限制接口不会新增存储能力。二、三大适配器模板原型1. stacktemplate class T, class Container dequeT class stack;对外接口push()、pop()、top()、empty()、size()只能在尾部操作入栈、出栈、取栈顶不能遍历、不能访问中间元素2. queuetemplate class T, class Container dequeT class queue;对外接口push()、pop()、front()、back()、empty()、size()尾插、头删只能取队首队尾不能遍历中间元素3. priority_queuetemplate class T, class Container vectorT, class Compare lessT class priority_queue;对外接口push()、pop()、top()、empty()、size()只允许取堆顶push/pop 内部自动做堆调整。三、底层容器更换规则适配器可以手动更换底层容器但必须满足接口要求stack底层可以用deque/vector/list只要支持尾插尾删、back ()stackint, vectorint st;queue底层不能用 vector queue 需要头删pop_front()vector 的头删效率极低而且 STL 不允许 vector 作为 queue 底层。 可选deque、listqueueint, listint q;priority_queue必须支持随机访问 []堆调整需要按下标找父子节点 ✅ 允许vector、deque❌ 禁止list没有随机访问priority_queueint, dequeint pq;面试题为什么 priority_queue 默认是 vectorstack/queue 默认 deque 答vector 连续内存随机访问快最适合堆的下标操作deque 头尾增删都是 O (1)不需要移动大量元素适合 stack、queue。四、适配器的共性特点没有迭代器不能遍历适配器刻意隐藏底层容器迭代器。stack/queue/priority_queue 不提供 begin () /end ()。设计目的强制遵守数据结构规则。栈就只能栈顶操作队列只能头尾操作禁止乱序遍历。 如果你拿到迭代器就可以随便修改中间元素破坏栈 / 队列 / 堆的性质。底层容器是适配器的成员就像你手写 priority_queue 里面Container _con;所有操作都是调用_con的成员函数。五、适配器对比表表格特性stackqueuepriority_queue规则LIFO 后进先出FIFO 先进先出按优先级出队默认底层dequedequevector插入位置尾部 push_back尾部 push_back尾部 push_back 向上堆调整删除位置尾部 pop_back头部 pop_front首尾交换 pop_back 向下堆调整取元素top () 栈顶front () 队首 back () 队尾top () 堆顶迭代器❌无❌无❌无模板参数T, ContainerT, ContainerT, Container, Compare 仿函数七、仿函数仿函数本质重载了operator()的类 / 结构体对象可以像函数一样去调用。也叫函数对象。1. 核心原理普通函数调用func(a,b)仿函数调用obj(a,b)看着像函数调用实际是调用这个对象里重载的operator()templateclass T class Less { public: bool operator()(const T x, const T y) { return x y; } };Lessint是类Lessint()是临时对象匿名仿函数com(a,b)等价com.operator()(a,b)Lessint lessObj; // 创建仿函数对象 cout lessObj(2,5); // 等价 lessObj.operator()(2,5)返回 true2. 仿函数 vs 普通函数表格仿函数类重载 operator ()普通函数状态可以保存成员变量携带状态不能存状态模板容易和 STL 算法配合类型推导友好函数指针类型推导麻烦内联编译器更容易内联效率高容易退化成函数调用写的Less/Greater就是 STL 风格的谓词仿函数返回 bool两个参数 → 二元谓词3. 二元谓词规则com(x,y)返回true的含义x 应该排在 y 的后面y 优先级更高y 放前面Lessint com; com(x,y) → x y 返回true // 含义x比y小x优先级更低y更大y要放到前面 → 降序排序Greaterint com; com(x,y) → x y 返回true // 含义x比y大x优先级更低y更小y放到前面 → 升序排序4. 仿函数两种使用方式方式 1匿名临时对象你 main 里用的BubbleSort(a,7, Lessint()); // Lessint() 创建一个临时对象传给模板参数Compare方式 2先定义对象再传入Lessint lessObj; BubbleSort(a,7, lessObj);5. 仿函数可以带状态举个例子统计比较次数templateclass T class LessCount { public: int count 0; bool operator()(const T x, const T y) { count; // 记录调用次数 return x y; } };手搓代码#pragma once #includeiostream #includevector #includeassert.h using namespace std; templateclass 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; } }; namespace cl { template class T,class Container vectorT,class Compare LessT class priority_queue { public: priority_queue() default;//强制编译器生成默认构造 //用一段迭代器区间去进行初始化 template class InputIterator priority_queue(InputIterator first, InputIterator last) :_con(first,last) { //向下调整建堆 //向下调整建堆是从最后一个非叶子节点开始即(_cin.size()-1-1)/2 这是一个父节点 for (int i (_con.size() - 1 - 1) / 2; i 0; i--) { adjust_down(i); } } void push(const T x) { _con.push_back(x); adjust_up(_con.size() - 1); } void pop() { assert(!empty()); swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjust_down(0); } const T top() { assert(!empty()); return _con[0]; } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: void adjust_up(int child) { Compare com; int parent (child - 1) / 2; while (child 0) { //if (_con[child] _con[parent]) //if(_con[parent]_con[child]) if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); child parent; parent (child - 1)/2; } else { break; } } } void adjust_down(int parent) { //建立一个仿函数对象 Compare com; size_t child 2 * parent 1; while(child _con.size()) { // 如果右孩子存在并且右孩子比左孩子更满足比较规则则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 (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); parent child; child 2 * parent 1; } else break; } } private: Container _con; }; }
