1. 项目概述为什么优先队列是算法学习的“分水岭”如果你刚开始接触C的STL容器学完vector、list、queue这些基础结构后下一个让你感觉“有点东西”的大概率就是priority_queue优先队列。它不像普通队列那样简单遵循“先进先出”而是让“优先级最高”的元素先出队。这个看似简单的规则变化背后却链接着数据结构与算法的核心思想——堆Heap。很多新手在刷LeetCode时遇到“前K个高频元素”、“合并K个有序链表”、“数据流的中位数”这类题目一看题解满屏的priority_queue瞬间就懵了。其实掌握了它你就相当于拿到了一把打开“中级算法”大门的钥匙。简单来说C中的priority_queue是一个容器适配器它默认将最大值置于队首大顶堆。你可以把它想象成一个“自动排序”的队列你只管往里push元素每次pop或查看top时得到的总是当前队列里优先级最高默认是最大的那个。它的底层通常由vector作为容器并使用堆算法来维护这种顺序因此插入和删除操作的时间复杂度是O(log n)获取队首元素是O(1)效率非常高。无论是为了应对面试中常考的堆相关题目还是为了在实际项目中处理需要动态排序的任务调度如CPU进程调度、带权路径搜索priority_queue都是一个必须熟练掌握的工具。接下来我会带你从零开始彻底搞懂它的里里外外。2. 核心原理与底层实现深度拆解2.1 堆优先队列的“发动机”要理解priority_queue必须先弄懂堆。堆是一种特殊的完全二叉树它满足一个关键性质对于大顶堆每个节点的值都大于或等于其子节点的值对于小顶堆每个节点的值都小于或等于其子节点的值。注意它只要求父节点和子节点之间有这个大小关系并不要求兄弟节点之间有序所以堆并不是完全排序的。priority_queue默认使用vector来隐式地表示这颗完全二叉树。给定一个下标为i的节点从0开始其父节点下标为(i - 1) / 2其左子节点下标为2 * i 1其右子节点下标为2 * i 2当我们向priority_queue插入(push)一个新元素时STL会执行“上浮”(sift-up)操作先将元素放在vector的末尾即完全二叉树的最后一个叶子节点位置然后不断与它的父节点比较。如果它比父节点“大”对于大顶堆就交换它们的位置直到它不大于父节点或到达根节点。这个过程保证了堆的性质在插入后依然成立。当我们从priority_queue删除(pop)队首元素即堆顶时操作稍复杂将堆顶元素vector[0]与最后一个叶子节点交换。删除现在的最后一个元素即原来的堆顶。对新的堆顶元素执行“下沉”(sift-down)操作不断将其与左右子节点中较大的那个比较如果它小于该子节点则交换直到它大于等于所有子节点或成为叶子节点。正是通过“上浮”和“下沉”这两个O(log n)的操作priority_queue在插入和删除时高效地维护了堆序。2.2 容器适配器priority_queue的独特身份priority_queue在STL中被定义为容器适配器。这意味着它“站在巨人的肩膀上”自身并不直接管理内存而是基于一个底层容器如vector或deque来构建其功能。你可以通过模板参数来指定这个底层容器。template class T, class Container vectorT, class Compare lesstypename Container::value_type class priority_queue;T: 队列中元素的类型。Container: 底层容器类型必须满足序列容器的要求并提供front()、push_back()、pop_back()等接口。默认是vectorT。Compare: 用于定义优先级的比较函数对象。默认是lessT这意味着使用运算符比较形成大顶堆因为堆顶是“最大”值。如果想得到小顶堆需要显式指定为greaterT。这种适配器设计模式的好处是代码复用和灵活性。priority_queue只关心堆算法的逻辑而内存分配、元素存储等脏活累活都交给了底层容器。这也是为什么priority_queue没有迭代器——它的访问顺序是由堆序决定的而不是插入顺序提供迭代器遍历会破坏其抽象。3. 从入门到精通priority_queue的完整使用指南3.1 基础操作创建、插入、访问与删除让我们从一个最简单的例子开始看看priority_queue的基本操作。#include iostream #include queue // 注意priority_queue 在 queue 头文件中 #include vector using namespace std; int main() { // 1. 创建一个默认的大顶堆存储int priority_queueint maxHeap; // 2. 插入元素 maxHeap.push(3); maxHeap.push(1); maxHeap.push(4); maxHeap.push(1); maxHeap.push(5); // 3. 访问堆顶元素优先级最高的元素 cout Top element: maxHeap.top() endl; // 输出 5 // 4. 删除堆顶元素 maxHeap.pop(); cout Top element after pop: maxHeap.top() endl; // 输出 4 // 5. 获取队列大小和判断是否为空 cout Size: maxHeap.size() endl; cout Is empty? (maxHeap.empty() ? Yes : No) endl; // 6. 遍历通过不断pop cout Elements in descending order: ; while (!maxHeap.empty()) { cout maxHeap.top() ; maxHeap.pop(); } // 输出: 4 3 1 1 cout endl; return 0; }注意priority_queue的pop()函数只删除队首元素并不返回它。你需要先用top()获取值再调用pop()删除。这是一个常见的踩坑点直接写int val maxHeap.pop();是编译错误的。3.2 如何构建一个小顶堆默认的priority_queue是大顶堆。但在很多算法场景如Dijkstra算法求最短路径、哈夫曼编码中我们需要的是小顶堆。这时就需要用到第三个模板参数——比较器(Compare)。// 方法一使用 greaterT 作为比较器需要包含 functional #include functional priority_queueint, vectorint, greaterint minHeap; minHeap.push(5); minHeap.push(2); minHeap.push(8); cout minHeap.top() endl; // 输出 2最小的在堆顶 // 方法二使用自定义比较函数对象或lambda表达式更灵活见下文这里的关键是理解比较器与堆序的关系。priority_queue会将“优先级最高”的元素放在堆顶。它通过比较器来判断两个元素的“优先级”。默认的lessT表示“小于”比较但在堆的“上浮”过程中如果当前节点“小于”父节点它就需要继续上浮。最终使得“最大”的元素即其他元素都“小于”它沉在堆底而“最小”的元素浮到堆顶了吗不恰恰相反。因为less比较下值大的元素在比较中返回false即“不小于”从而停止上浮最终留在了堆顶。所以less对应的是大顶堆。同理greater对应小顶堆。你可以这样记忆比较器决定的是“谁应该排在更后面”堆顶是“最前面”。用less时大的元素“不应该”排在小的后面所以大的在前面堆顶用greater时小的元素“不应该”排在大的后面所以小的在前面堆顶。3.3 处理自定义类型比较规则的制定当priority_queue存储的是自定义的结构体或类时我们必须告诉它如何比较两个对象的“优先级”。有两种主流方式方式一重载运算符适用于大顶堆如果你只需要大顶堆且认为“小于”运算符能定义你的优先级逻辑这是最简洁的方式。struct Task { int priority; string name; // 重载 运算符注意我们希望优先级数字大的先出队 bool operator(const Task other) const { // 注意这里对于大顶堆我们希望 priority 值大的“更小” // 不对在默认 less 比较下返回 true 表示当前对象“小于”other应该排在 other 后面。 // 我们希望 priority 大的排在前面堆顶所以当 this-priority 较小时它应该排在后面。 return this-priority other.priority; // 这是常见的错误写法 // 正确的逻辑是如果 this-priority 小于 other.priority说明 this 的优先级更低应该排在后面。 // 对于大顶堆值大的元素应该在前。所以当 this-priority other.priority 时this 应该排在 other 后面即 this other 为 true。 // 所以上面的写法是对的。但很容易绕晕。 // 更直观的理解在默认大顶堆下重载的 应该定义“什么情况下当前对象比另一个对象的优先级低”。 // 如果 this.priority 值小则优先级低所以 this other 返回 true。 } }; priority_queueTask taskQueue; taskQueue.push({3, Low Pri Task}); taskQueue.push({8, High Pri Task}); cout taskQueue.top().name endl; // 输出 High Pri Task方式二使用自定义比较类或函数对象推荐更清晰灵活这种方式更通用可以定义任意复杂的比较逻辑也便于切换大小顶堆。struct Task { int priority; string name; }; // 自定义比较类仿函数 struct CompareTaskPriority { // 定义“优先级低”的规则 bool operator()(const Task a, const Task b) const { // 我们希望 priority 值小的优先级低 return a.priority b.priority; // 对于大顶堆这是正确的 // 这个函数返回 true意味着 a 的优先级低于 ba 应该排在 b 后面。 } }; // 使用自定义比较类 priority_queueTask, vectorTask, CompareTaskPriority maxHeapTask; // 如果想实现小顶堆priority值小的先出队只需修改比较逻辑 struct CompareTaskPriorityMin { bool operator()(const Task a, const Task b) const { return a.priority b.priority; // 注意符号反转 // 当 a.priority b.priority 时a 的优先级更低因为值更大应该排在后面。 } }; priority_queueTask, vectorTask, CompareTaskPriorityMin minHeapTask;方式三使用Lambda表达式C11及以上非常简洁在函数内部你可以用Lambda快速定义比较器但语法稍显复杂。auto cmp [](const Task left, const Task right) { // 定义“左边优先级低于右边”的规则 return left.priority right.priority; // 大顶堆规则 }; // 注意Lambda的类型需要显式指定或者使用 decltype并且priority_queue的构造函数也需要传入比较器对象 priority_queueTask, vectorTask, decltype(cmp) taskQueue(cmp); // 或者更直观地使用函数指针类型但Lambda需无捕获 // priority_queueTask, vectorTask, bool(*)(const Task, const Task) taskQueue(cmp);实操心得对于自定义类型我强烈推荐方式二自定义比较类。它逻辑清晰可读性强并且该比较类可以在多个地方复用。重载运算符虽然方便但一旦你需要小顶堆或者另一种排序规则就会很尴尬因为运算符的含义被固化了。而Lambda表达式在局部使用很灵活但作为类成员或需要复用时就不太方便。3.4 底层容器的选择与性能考量priority_queue默认使用vector作为底层容器。为什么是vector而不是deque或listvector在尾部插入(push_back)和删除(pop_back)是分摊常数时间O(1)这与堆操作的“上浮”从尾部开始和“下沉”需要交换尾部元素完美契合。并且vector的内存连续缓存友好访问速度快。因此它是默认且最佳的选择。deque同样支持push_back和pop_back但它的内存是分段的。虽然也能用但性能通常略逊于vector因为堆算法中频繁的随机访问通过下标计算父节点/子节点在deque上可能引发更多的缓存未命中。list绝对不能使用。list不支持随机访问无法通过下标在O(1)时间内找到父节点或子节点破坏了堆算法的基础。STL的priority_queue也不支持用list作为底层容器。除非有非常特殊的理由否则请始终坚持使用默认的vector。4. 实战应用算法与面试题精讲理解了基本操作我们来看看priority_queue如何解决实际问题。这里我挑几个最经典的场景。4.1 场景一Top K 问题前K个最大/最小元素这是priority_queue最典型的应用。例如LeetCode 215题“数组中的第K个最大元素”。暴力解法是排序然后取第K个时间复杂度O(n log n)。使用priority_queue可以将复杂度优化到O(n log k)。思路维护一个大小为K的小顶堆。遍历数组将元素插入小顶堆。如果堆的大小超过K就弹出堆顶当前堆中最小的元素。遍历结束后堆顶元素就是第K个最大的元素因为比它大的K-1个元素都在堆里且它自己是堆里最小的。int findKthLargest(vectorint nums, int k) { // 定义一个小顶堆 priority_queueint, vectorint, greaterint minHeap; for (int num : nums) { minHeap.push(num); if (minHeap.size() k) { minHeap.pop(); // 弹出最小的保持堆里是最大的k个 } } return minHeap.top(); // 堆顶是这k个最大元素中最小的即第k大 }为什么用小顶堆因为我们的目标是保留最大的K个元素。小顶堆的堆顶是这K个元素里最小的那个。每当新来的元素比堆顶大我们就替换掉堆顶这个最小的从而保证堆里始终是迄今为止看到的最大的K个。如果使用大顶堆你需要存储所有元素然后弹出前K-1个效率更低。变种求前K个高频元素LeetCode 347这时元素是pair频率, 数值我们需要按频率排序。思路完全一致只是比较的对象是频率。vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int freqMap; for (int num : nums) freqMap[num]; // 小顶堆比较频率 auto cmp [](const pairint, int a, const pairint, int b) { return a.second b.second; // 频率小的优先级高放在堆顶方便弹出 }; priority_queuepairint, int, vectorpairint, int, decltype(cmp) minHeap(cmp); for (auto [num, freq] : freqMap) { minHeap.push({num, freq}); if (minHeap.size() k) { minHeap.pop(); } } vectorint result; while (!minHeap.empty()) { result.push_back(minHeap.top().first); minHeap.pop(); } reverse(result.begin(), result.end()); // 因为是小顶堆弹出顺序是频率升序需要反转 return result; }4.2 场景二多路归并合并K个有序链表LeetCode 23题“合并K个升序链表”。暴力解法是两两合并时间复杂度高。使用priority_queue可以优雅地在O(N log k)内解决其中N是总节点数k是链表条数。思路使用一个小顶堆初始时将每条链表的头节点放入堆中。每次弹出堆顶当前所有头节点中最小的那个将其接入结果链表然后将该节点的下一个节点如果存在压入堆中。如此循环直到堆为空。struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; struct CompareNode { bool operator()(ListNode* a, ListNode* b) { return a-val b-val; // 小顶堆 } }; ListNode* mergeKLists(vectorListNode* lists) { priority_queueListNode*, vectorListNode*, CompareNode minHeap; // 初始化堆放入所有非空链表的头节点 for (ListNode* head : lists) { if (head) minHeap.push(head); } ListNode dummy(0); // 哑节点简化链表操作 ListNode* tail dummy; while (!minHeap.empty()) { ListNode* smallest minHeap.top(); minHeap.pop(); tail-next smallest; tail tail-next; if (smallest-next) { minHeap.push(smallest-next); } } return dummy.next; }这个解法非常精妙它本质上是将K个有序序列的合并问题转化为了在K个当前候选元素中不断选择最小值的问题priority_queue完美胜任了“动态选择最小值”这个角色。4.3 场景三数据流的中位数动态维护LeetCode 295题“数据流的中位数”。要求设计一个数据结构能随时向其中添加数字并能快速返回当前所有数字的中位数。思路用两个堆来维护数据流。maxHeap大顶堆存储数据流中较小的一半数字。堆顶是这一半里最大的。minHeap小顶堆存储数据流中较大的一半数字。堆顶是这一半里最小的。平衡规则保证两个堆的大小之差不超过1。且maxHeap的所有元素 minHeap的所有元素。这样中位数就可以通过两个堆的堆顶快速计算如果总元素数为奇数中位数就是元素多的那个堆的堆顶。如果为偶数中位数是两个堆顶的平均值。class MedianFinder { private: priority_queueint maxHeap; // 较小的一半 priority_queueint, vectorint, greaterint minHeap; // 较大的一半 public: MedianFinder() {} void addNum(int num) { // 先加入 maxHeap maxHeap.push(num); // 保证 maxHeap 的堆顶 minHeap 的堆顶 // 如果不满足就交换堆顶 if (!minHeap.empty() maxHeap.top() minHeap.top()) { int maxTop maxHeap.top(); maxHeap.pop(); int minTop minHeap.top(); minHeap.pop(); maxHeap.push(minTop); minHeap.push(maxTop); } // 平衡两个堆的大小保证差值 1 if (maxHeap.size() minHeap.size() 1) { minHeap.push(maxHeap.top()); maxHeap.pop(); } else if (minHeap.size() maxHeap.size() 1) { maxHeap.push(minHeap.top()); minHeap.pop(); } } double findMedian() { if (maxHeap.size() minHeap.size()) { return (maxHeap.top() minHeap.top()) / 2.0; } else if (maxHeap.size() minHeap.size()) { return maxHeap.top(); } else { return minHeap.top(); } } };这个设计体现了priority_queue在动态数据维护中的强大能力插入操作O(log n)查询中位数O(1)效率非常高。5. 避坑指南与性能优化实战5.1 常见错误与误区混淆pop()和top()如前所述pop()不返回值。这是一个编译错误但新手容易犯。误用比较器导致错误的堆序这是最烧脑的坑。一定要反复测试你的比较逻辑。一个简单的测试方法是插入一组已知数据然后连续pop并输出看顺序是否符合预期。遍历priority_queuepriority_queue没有迭代器你不能用for (auto it : pq)来遍历。唯一的“遍历”方式是不断pop但这会清空队列。如果只是想查看内容而不修改需要先拷贝一份。在自定义比较器中修改元素比较函数必须是纯函数不应有副作用如修改比较对象。否则会导致未定义行为破坏堆的结构。存储指针时的陷阱如果priority_queue存储的是指针如ListNode*比较器比较的是指针地址而不是指针指向的对象。你必须自定义比较器来解引用并比较实际值。// 错误示例比较指针地址 priority_queueListNode* pq; // 这会按指针地址排序毫无意义 // 正确做法提供自定义比较器 auto cmp [](ListNode* a, ListNode* b) { return a-val b-val; }; priority_queueListNode*, vectorListNode*, decltype(cmp) pq(cmp);5.2 性能优化技巧预先分配内存对于vector底层如果你能预估priority_queue的最大规模可以在使用前通过底层容器的reserve方法来预留空间避免多次动态扩容带来的开销。但注意priority_queue没有直接提供reserve接口你需要通过构造函数传递一个已经预留好空间的容器。vectorint vec; vec.reserve(10000); // 预留10000个元素的空间 priority_queueint pq(lessint(), std::move(vec)); // 使用移动语义 // 注意这样构造后pq的初始底层容器就是vec且已预留空间。使用emplace代替pushC11对于自定义类型emplace可以直接在容器内构造对象避免一次额外的拷贝或移动操作。struct Point { int x; int y; Point(int a, int b) : x(a), y(b) {} }; priority_queuePoint pq; pq.push(Point(1, 2)); // 构造临时对象然后拷贝/移动到容器 pq.emplace(1, 2); // 直接在容器内存中构造Point(1, 2)更高效批量建堆如果你已经有一个包含所有数据的容器如vector想直接基于它构建堆使用priority_queue的构造函数效率更高其时间复杂度是O(n)而不是重复push的O(n log n)。vectorint data {3,1,4,1,5,9,2,6}; // 方法一使用迭代器范围构造函数 priority_queueint pq(data.begin(), data.end()); // O(n)建堆 // 方法二先构造一个空的然后使用底层容器的范围赋值较少用 // priority_queueint pq; // pq.c.assign(data.begin(), data.end()); // c是底层容器但它是protected成员外部不能直接访问。所以方法一更实用。选择正确的数据结构priority_queue擅长快速获取最大值/最小值并进行动态更新。但如果你的需求还包括快速查找任意元素、删除非堆顶元素那么priority_queue就不合适了你可能需要考虑set或multiset基于红黑树查找、插入、删除都是O(log n)。5.3 与相关数据结构的对比为了在正确场景选择正确工具了解priority_queue的“兄弟姐妹”很重要。特性priority_queueset/multisetmap/multimap底层实现堆 (Heap)红黑树 (Red-Black Tree)红黑树 (Red-Black Tree)排序依据优先级可自定义比较器键值自动排序键值自动排序访问顶部O(1)O(log n) (begin()/rbegin())O(log n) (begin()/rbegin())插入元素O(log n)O(log n)O(log n)删除顶部O(log n)O(log n) (erase(begin()))O(log n) (erase(begin()))删除任意元素不支持O(log n)O(log n)查找任意元素不支持O(log n)O(log n)是否允许重复是multiset允许set不允许multimap允许map不允许主要用途调度、Top K、贪心算法需要有序且可能查找/删除任意元素的集合需要有序键值对关联并可能查找/删除任意键核心选择建议如果你只需要不断获取并移除当前最大/最小的元素用priority_queue。如果你还需要频繁查找、插入、删除集合中的任意元素并且希望集合始终保持有序用set/map。如果数据量极小比如10个元素线性查找和排序可能更简单但priority_queue的代码通常更清晰。6. 进阶手撕一个简易priority_queue理解原理最好的方式就是自己实现一个。下面我们实现一个模板化的简易版MyPriorityQueue支持大顶堆和自定义比较器。#include vector #include functional // for std::less template typename T, typename Container std::vectorT, typename Compare std::lesstypename Container::value_type class MyPriorityQueue { private: Container c; // 底层容器 Compare comp; // 比较函数对象 // 上浮操作 void siftUp(size_t idx) { while (idx 0) { size_t parent (idx - 1) / 2; if (!comp(c[parent], c[idx])) { // 如果父节点“不小于”当前节点满足堆性质停止 break; } std::swap(c[parent], c[idx]); idx parent; } } // 下沉操作 void siftDown(size_t idx) { size_t size c.size(); while (true) { size_t left 2 * idx 1; size_t right 2 * idx 2; size_t largest idx; if (left size comp(c[largest], c[left])) { largest left; } if (right size comp(c[largest], c[right])) { largest right; } if (largest idx) { break; } std::swap(c[idx], c[largest]); idx largest; } } // 建堆Floyd算法O(n) void makeHeap() { if (c.size() 1) return; for (int i (c.size() - 2) / 2; i 0; --i) { siftDown(i); } } public: // 构造函数 MyPriorityQueue() default; explicit MyPriorityQueue(const Compare compare) : comp(compare) {} template typename InputIt MyPriorityQueue(InputIt first, InputIt last, const Compare compare Compare()) : c(first, last), comp(compare) { makeHeap(); } // 核心接口 bool empty() const { return c.empty(); } size_t size() const { return c.size(); } const T top() const { if (empty()) { throw std::out_of_range(MyPriorityQueue is empty); } return c.front(); } void push(const T value) { c.push_back(value); siftUp(c.size() - 1); } void push(T value) { c.push_back(std::move(value)); siftUp(c.size() - 1); } template class... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); siftUp(c.size() - 1); } void pop() { if (empty()) { throw std::out_of_range(MyPriorityQueue is empty); } std::swap(c.front(), c.back()); c.pop_back(); if (!empty()) { siftDown(0); } } }; // 测试代码 int main() { MyPriorityQueueint maxHeap; maxHeap.push(3); maxHeap.push(1); maxHeap.push(4); std::cout maxHeap.top() std::endl; // 4 maxHeap.pop(); std::cout maxHeap.top() std::endl; // 3 // 使用自定义比较器实现小顶堆 MyPriorityQueueint, std::vectorint, std::greaterint minHeap; minHeap.push(3); minHeap.push(1); minHeap.push(4); std::cout minHeap.top() std::endl; // 1 return 0; }通过这个简单的实现你可以更深刻地理解上浮、下沉、建堆这些核心操作是如何协同工作的以及比较器comp是如何在内部被调用来决定堆序的。自己动手写一遍胜过看十遍原理说明。