企业官网建设流程全解析

用priority_queue搞定LeetCode前K个高频元素：C++ STL实战解法与避坑指南

在算法面试和日常刷题中，"Top K"问题几乎是必考题。LeetCode 347题要求找出数组中出现频率前K高的元素，这类问题考验的不仅是基础编码能力，更是对数据结构和算法选择的深刻理解。本文将带你用C++ STL中的std::priority_queue（优先队列）高效解决这个问题，重点剖析为什么小顶堆比大顶堆更适合此场景，以及如何避免实际编码中的常见陷阱。

1. 理解问题本质与数据结构选择

遇到"前K个高频元素"问题时，新手常犯的错误是直接排序整个频率表。虽然这种方法能得到正确答案，但其O(n log n)的时间复杂度并不是最优解。更聪明的做法是利用堆（Heap）这种数据结构，将时间复杂度优化到O(n log k)。

为什么是堆？

堆是一种特殊的完全二叉树，满足以下性质：

• 大顶堆：每个节点的值都大于或等于其子节点的值
• 小顶堆：每个节点的值都小于或等于其子节点的值

堆的核心优势在于：

• 插入/删除操作的时间复杂度为O(log n)
• 获取堆顶元素（最大值或最小值）的时间复杂度为O(1)

对于Top K问题，我们只需要维护当前频率最高的K个元素，堆的这两个特性正好契合需求。

大顶堆 vs 小顶堆的选择

这里有个关键决策点：该用大顶堆还是小顶堆？让我们用实际数据对比：

假设有元素频率表：{A:3, B:5, C:1, D:4, E:2}，要求找出前2个高频元素。

大顶堆方案：

1. 将所有元素插入大顶堆：[B:5, D:4, A:3, E:2, C:1]
2. 取出前K个元素：B:5, D:4

小顶堆方案：

1. 维护一个大小为K=2的小顶堆：
   • 插入B:5 →[B:5]
   • 插入D:4 →[D:4, B:5]（堆调整）
   • 遇到A:3时，因为3 < 堆顶的4，跳过
   • 同理跳过E:2和C:1
2. 最终堆中保留的就是[D:4, B:5]

虽然两种方案都能得到正确答案，但小顶堆的空间复杂度是O(k)，而大顶堆是O(n)。当n远大于k时（这是常见情况），小顶堆的优势就非常明显了。

提示：在面试中，面试官通常会追问"为什么选择小顶堆而不是大顶堆"，这时你需要清楚解释空间复杂度的差异。

2. std::priority_queue深度解析

C++ STL中的std::priority_queue本质上是一个堆的实现，默认情况下是大顶堆。理解它的模板参数对正确使用至关重要。

2.1 priority_queue的模板参数

priority_queue的完整声明形式为：

template< class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue;

三个模板参数的含义：

1. T：存储的元素类型
2. Container：底层容器，必须是随机访问容器（如vector或deque）
3. Compare：比较函数对象，决定是大顶堆还是小顶堆

2.2 构造大小顶堆的两种方式

大顶堆构造：

// 默认方式（使用less比较函数） priority_queue<int> max_heap1; // 显式指定方式 priority_queue<int, vector<int>, less<int>> max_heap2;

小顶堆构造：

// 必须显式指定greater比较函数 priority_queue<int, vector<int>, greater<int>> min_heap;

关键点在于理解less和greater的实际效果：

• less：形成大顶堆（因为默认是"<"比较，堆顶是"最大"元素）
• greater：形成小顶堆（因为">"比较，堆顶是"最小"元素）

2.3 自定义比较函数

对于复杂数据类型，我们需要自定义比较函数。以本题为例，我们需要根据元素的频率进行比较：

struct Compare { bool operator()(const pair<int, int>& a, const pair<int, int>& b) { return a.second > b.second; // 小顶堆 } }; priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> min_heap;

注意比较函数中的>符号，这决定了是小顶堆。如果写反了，整个算法就会出错。

3. 完整解题步骤与代码实现

现在我们将所有知识点整合，解决LeetCode 347题。

3.1 算法步骤拆解

1. 统计频率：遍历数组，用哈希表记录每个元素的出现次数
2. 构建小顶堆：维护一个大小为K的小顶堆
   • 当堆大小小于K时，直接插入元素
   • 当堆大小等于K时，比较当前元素频率与堆顶元素频率
     • 如果当前频率更大，弹出堆顶，插入当前元素
     • 否则跳过
3. 收集结果：将堆中元素输出

3.2 完整实现代码

#include <vector> #include <queue> #include <unordered_map> #include <algorithm> using namespace std; vector<int> topKFrequent(vector<int>& nums, int k) { // 1. 统计频率 unordered_map<int, int> freq_map; for (int num : nums) { freq_map[num]++; } // 2. 定义比较函数和小顶堆 auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) { return a.second > b.second; }; priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> min_heap(cmp); // 3. 维护大小为K的小顶堆 for (const auto& entry : freq_map) { if (min_heap.size() < k) { min_heap.push(entry); } else if (entry.second > min_heap.top().second) { min_heap.pop(); min_heap.push(entry); } } // 4. 收集结果 vector<int> result; while (!min_heap.empty()) { result.push_back(min_heap.top().first); min_heap.pop(); } reverse(result.begin(), result.end()); // 因为是小顶堆，需要反转 return result; }

3.3 复杂度分析

• 时间复杂度：O(n log k)
  • 统计频率：O(n)
  • 堆操作：最坏情况下每个元素都要入堆一次，每次入堆O(log k)
• 空间复杂度：O(n + k)
  • 哈希表存储频率：O(n)
  • 堆存储元素：O(k)

4. 常见陷阱与调试技巧

即使理解了算法原理，实际编码时仍可能遇到各种问题。以下是几个常见陷阱及解决方法：

4.1 比较函数写反

// 错误示例：本意是小顶堆，但比较方向写反了 auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) { return a.second < b.second; // 实际上变成了大顶堆 };

调试技巧：插入测试数据{1:3, 2:2, 3:1}，检查堆顶元素是否是频率最小的。

4.2 忘记处理容器参数

// 错误示例：忘记指定底层容器 priority_queue<pair<int, int>, decltype(cmp)> min_heap(cmp); // 编译错误

解决方法：完整指定三个模板参数：

priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> min_heap(cmp);

4.3 结果顺序问题

小顶堆输出的结果是频率从小到大排列的，而题目通常要求从高到低排列。忘记反转结果是一个常见疏忽：

// 在收集结果后需要反转 reverse(result.begin(), result.end());

4.4 处理边界条件

• 空输入数组
• K值大于数组不同元素的数量
• K值为0或负数

完善的代码应该处理这些边界情况：

if (nums.empty() || k <= 0) return {}; k = min(k, static_cast<int>(freq_map.size()));

5. 扩展应用与变种问题

掌握了这个解法后，你可以轻松应对多种Top K问题的变种：

5.1 前K个低频元素

只需修改比较函数，将小顶堆改为大顶堆：

auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) { return a.second < b.second; // 大顶堆 };

5.2 处理流数据

当数据以流的形式到达时（不能一次性获取所有数据），堆的解决方案依然适用：

class TopKTracker { private: priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> min_heap; unordered_map<int, int> freq_map; int k; public: TopKTracker(int k) : k(k) {} void add(int num) { freq_map[num]++; if (min_heap.size() < k) { min_heap.push({num, freq_map[num]}); } else if (freq_map[num] > min_heap.top().second) { min_heap.pop(); min_heap.push({num, freq_map[num]}); } } vector<int> getTopK() { vector<int> result; // ... 同前 ... return result; } };

5.3 其他Top K问题变种