1. 优先级队列基础概念解析
优先级队列（Priority Queue）是一种特殊的队列数据结构，它不同于普通的先进先出（FIFO）队列，而是根据元素的优先级来决定出队顺序。在C++标准库中，优先级队列是通过堆（Heap）数据结构实现的，这使得它能够在O(1)时间内获取最高（或最低）优先级的元素，同时在O(log n)时间内完成元素的插入和删除操作。
优先级队列的核心特性在于它总是保证队列首部的元素是当前队列中优先级最高的。这个特性使得它在许多算法问题中成为高效的选择，特别是那些需要频繁获取极值的场景。在C++中，优先级队列是通过<queue>头文件中的priority_queue模板类提供的，它默认实现为大根堆（最大堆），即优先级高的元素（值大的元素）会先出队。
注意：虽然优先级队列的底层实现通常是堆，但从抽象数据类型的角度来看，我们更关注它的接口行为而非具体实现。这种抽象让我们可以专注于解决问题，而不必每次都手动实现堆结构。
2. 优先级队列的典型应用场景
2.1 最后一块石头的重量问题
这个问题描述如下：有一堆石头，每块石头的重量都是正整数。每次我们选择两块最重的石头进行粉碎，如果重量相同则都粉碎，否则较重的石头会被较轻石头的重量所抵消。重复这个过程直到剩下最后一块石头（或没有石头）。
使用优先级队列可以优雅地解决这个问题：
class Solution { public: int lastStoneWeight(vector<int>& stones) { priority_queue<int> q; for(auto e:stones) q.push(e); // 将所有石头放入大根堆 while(q.size()>1){ int a = q.top(); q.pop(); // 取出最重的石头 int b = q.top(); q.pop(); // 取出次重的石头 if(a != b) q.push(a-b); // 如果重量不同，将差值放回堆中 } return q.size() ? q.top() : 0; // 返回最后剩下的石头重量或0 } };这个解法的时间复杂度为O(n log n)，因为每个插入和删除操作都需要O(log n)时间，而最坏情况下我们需要进行n次这样的操作。空间复杂度为O(n)，用于存储优先级队列。
2.2 数据流中的第K大元素
设计一个类来高效地找到数据流中第K大的元素。这个问题特别适合使用最小堆来解决，因为我们需要维护前K大的元素，而最小堆的顶部正好是这K个元素中最小的，也就是第K大的元素。
class KthLargest { priority_queue<int, vector<int>, greater<int>> heap; // 最小堆 int _k; public: KthLargest(int k, vector<int>& nums) { _k = k; for(auto x : nums){ heap.push(x); if(heap.size() > _k) heap.pop(); // 保持堆的大小不超过k } } int add(int val) { heap.push(val); if(heap.size() > _k) heap.pop(); // 移除最小的元素以保持堆大小 return heap.top(); // 堆顶即为第K大元素 } };这种实现方式的时间复杂度为O(n log k)初始化，O(log k)每次添加操作。空间复杂度为O(k)，因为我们只需要存储前k大的元素。
3. 优先级队列的高级应用
3.1 前K个高频单词
这个问题要求我们找出出现频率最高的前k个单词，当频率相同时按字典序排列。这需要自定义优先级队列的比较函数：
class Solution { typedef pair<string, int> word_freq; struct comparator { bool operator()(const word_freq& a, const word_freq& b) { if(a.second == b.second) { return a.first < b.first; // 频率相同，字典序大的在前 } return a.second > b.second; // 频率小的在前 } }; public: vector<string> topKFrequent(vector<string>& words, int k) { unordered_map<string, int> freq_map; for(auto& word : words) freq_map[word]++; priority_queue<word_freq, vector<word_freq>, comparator> heap; for(auto& entry : freq_map){ heap.push(entry); if(heap.size() > k) heap.pop(); // 保持堆的大小为k } vector<string> result(k); for(int i = k-1; i >= 0; i--){ // 因为堆顶是最小元素，需要逆序填充 result[i] = heap.top().first; heap.pop(); } return result; } };这个解法的时间复杂度为O(n log k)，空间复杂度为O(n)。我们首先统计每个单词的频率（O(n)），然后使用大小为k的堆来处理这些频率（O(n log k)）。
3.2 数据流的中位数查找
中位数是排序后位于中间位置的数。对于数据流问题，我们需要动态维护中位数。使用两个堆（一个大根堆和一个小根堆）可以高效解决这个问题：
class MedianFinder { priority_queue<int> left; // 大根堆，存储较小的一半 priority_queue<int, vector<int>, greater<int>> right; // 小根堆，存储较大的一半 public: MedianFinder() {} void addNum(int num) { if(left.size() == right.size()){ if(left.empty() || num < left.top()){ left.push(num); } else { right.push(num); left.push(right.top()); right.pop(); } } else { if(num <= left.top()){ right.push(left.top()); left.pop(); left.push(num); } else { right.push(num); } } } double findMedian() { if(left.size() == right.size()) return (left.top() + right.top()) / 2.0; else return left.top(); } };这种实现保证了插入操作的时间复杂度为O(log n)，查找中位数的时间复杂度为O(1)。关键在于保持两个堆的大小平衡：要么大小相等，要么左堆比右堆多一个元素。
4. 优先级队列的实现原理与性能分析
4.1 堆数据结构基础
优先级队列通常使用二叉堆实现。二叉堆是一种完全二叉树，满足堆性质：对于最大堆，每个节点的值都大于或等于其子节点的值；对于最小堆，则相反。
堆的主要操作及其时间复杂度：
- 插入（push）：O(log n)
- 删除顶部元素（pop）：O(log n)
- 获取顶部元素（top）：O(1)
在C++中，priority_queue默认使用vector作为底层容器，并通过一系列堆算法（如push_heap、pop_heap）来维护堆性质。
4.2 自定义比较函数
当我们需要非标准的排序方式时，可以通过提供自定义比较函数来实现。比较函数应该严格弱序（strict weak ordering），即满足：
- 非自反性：comp(a, a) == false
- 非对称性：如果comp(a, b) == true，则comp(b, a) == false
- 可传递性：如果comp(a, b) == true且comp(b, c) == true，则comp(a, c) == true
例如，要实现一个存储pair的最小堆，其中先按second排序，second相同时按first排序：
struct Compare { bool operator()(const pair<int, int>& a, const pair<int, int>& b) { if(a.second == b.second) return a.first > b.first; return a.second > b.second; } }; priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;5. 优先级队列的实战技巧与常见问题
5.1 性能优化技巧
预留空间：如果知道优先级队列的大致大小，可以先调用
reserve来避免多次重新分配内存。vector<int> vec; vec.reserve(1000); // 预留空间 priority_queue<int> pq(less<int>(), move(vec));批量构建堆：当有所有初始元素时，使用构造函数一次性构建堆比逐个插入更高效（O(n) vs O(n log n)）。
vector<int> elements = {...}; priority_queue<int> pq(elements.begin(), elements.end());使用emplace：对于复杂对象，使用
emplace可以避免不必要的拷贝。priority_queue<pair<int, string>> pq; pq.emplace(42, "answer"); // 直接在堆中构造对象
5.2 常见问题排查
堆顶元素不符合预期：
- 检查比较函数是否正确实现
- 确认使用的是最大堆还是最小堆
- 对于自定义类型，确保比较操作定义正确
性能问题：
- 避免频繁的插入删除操作，考虑批量处理
- 对于固定大小的优先级队列，考虑使用
std::make_heap系列函数
内存问题：
- 大容量优先级队列可能消耗大量内存，考虑使用更紧凑的数据结构
- 对于基本类型，使用
vector作为底层容器通常比deque更高效
提示：在解决算法问题时，优先级队列常常与贪心算法结合使用。当问题涉及"每次取最大/最小元素"的操作模式时，优先考虑优先级队列是否能简化问题。
6. 优先级队列的变体与扩展应用
6.1 双端优先级队列
有时我们需要同时支持获取最大值和最小值的操作。这可以通过维护两个堆来实现，或者使用更专门的数据结构如区间堆。
class DualPriorityQueue { priority_queue<int> max_heap; priority_queue<int, vector<int>, greater<int>> min_heap; unordered_map<int, int> count; int size = 0; void clean() { while(!max_heap.empty() && count[max_heap.top()] == 0) max_heap.pop(); while(!min_heap.empty() && count[min_heap.top()] == 0) min_heap.pop(); } public: void push(int x) { max_heap.push(x); min_heap.push(x); count[x]++; size++; } int pop_max() { clean(); if(size == 0) throw runtime_error("Empty queue"); int x = max_heap.top(); max_heap.pop(); count[x]--; size--; return x; } int pop_min() { clean(); if(size == 0) throw runtime_error("Empty queue"); int x = min_heap.top(); min_heap.pop(); count[x]--; size--; return x; } };6.2 带更新的优先级队列
标准的优先级队列不支持高效的更新操作。当需要更新元素优先级时，可以考虑以下方法：
- 使用
std::set，它支持插入、删除和查找，且保持元素有序 - 使用懒惰删除策略：标记元素为已删除，在实际访问时跳过
- 使用专门的优先级队列实现如斐波那契堆（虽然C++标准库未提供）
template <typename T> class UpdatablePriorityQueue { set<pair<int, T>> queue; unordered_map<T, int> priorities; public: void push_or_update(T element, int priority) { if(priorities.count(element)) { queue.erase({priorities[element], element}); } priorities[element] = priority; queue.insert({priority, element}); } T pop() { if(queue.empty()) throw runtime_error("Empty queue"); T element = queue.begin()->second; queue.erase(queue.begin()); priorities.erase(element); return element; } bool empty() const { return queue.empty(); } };在实际工程中，选择哪种优先级队列实现取决于具体的应用场景和性能需求。理解各种实现的优缺点有助于我们在不同情况下做出合适的选择。
