### C++之常见顶堆问题汇总
在计算机科学与编程领域中，顶堆（优先队列）是一种非常实用的数据结构，常被应用于多种算法场景之中，尤其是在解决与排序相关的问题时更为常见。本文将从顶堆的基础知识入手，详细介绍其在C++中的实现方式，并通过两个LeetCode题目来具体展示如何利用顶堆解决问题。
#### 一、顶堆基础知识
##### 1. 底层原理
顶堆是一种特殊的树形数据结构，其中每个父节点的关键值要么大于（对于大顶堆）或小于（对于小顶堆）它的子节点的关键值。这种性质使得堆的顶部（根节点）始终包含最大或最小的元素，这为快速访问最大或最小元素提供了便利。在C++标准库中，`priority_queue`提供了堆的封装，它支持高效的插入和删除操作，且默认情况下实现了大顶堆。
##### 2. C++中的顶堆实现
- **大顶堆**：默认情况下，`priority_queue`就是一个大顶堆，用于存储元素时，默认按照降序排列。
```cpp
priority_queue<int> que;
que.push(1);
que.push(3);
que.push(2);
// Top element is 3 (followed by 2 and 1)
```
- **小顶堆**：可以通过传递第三个模板参数`greater<int>`来实现小顶堆，此时堆会按照升序排列元素。
```cpp
priority_queue<int, vector<int>, greater<int>> que;
que.push(1);
que.push(3);
que.push(2);
// Top element is 1 (followed by 2 and 3)
```
- **自定义数据类型和比较规则**：当需要处理非基本数据类型时，可以自定义比较规则来实现特定需求的堆。
```cpp
auto cmp = [](const pair<int, int> a, const pair<int, int> b) -> bool {
return a.first + a.second > b.first + b.second;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> que(cmp);
```
上述例子中，我们定义了一个lambda函数`cmp`来比较两个`pair<int, int>`类型的元素。`que`是一个按照元素的两个整数之和从大到小排序的大顶堆。
#### 二、典型LeetCode题目解析
##### 1. 剑指Offer II 059. 数据流的第K大数值
题目链接：[剑指Offer II 059. 数据流的第K大数值](https://leetcode-cn.com/problems/jBjn9C/)
**题目描述**：设计一个找到数据流中第`k`大元素的类（class）。注意是排序后的第`k`大元素，不是第`k`个不同的元素。请实现`KthLargest`类：
- `KthLargest(int k, int[] nums)` 使用整数`k`和整数流`nums`初始化对象。
- `int add(int val)` 将`val`插入数据流`nums`后，返回当前数据流中第`k`大的元素。
**示例**：
```cpp
输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]
```
**思路**：为了高效地获取数据流中的第`k`大元素，我们可以维护一个大小为`k`的小顶堆。每次向堆中添加新元素时，如果堆的大小超过`k`，则弹出堆顶元素，这样堆顶始终保存着第`k`大的元素。
**代码实现**：
```cpp
class KthLargest {
public:
priority_queue<int, vector<int>, greater<int>> que;
int k;
KthLargest(int k, vector<int>& nums) {
this->k = k;
for (int i = 0; i < nums.size(); i++) {
if (que.size() >= k) {
que.push(nums[i]);
que.pop();
} else {
que.push(nums[i]);
}
}
}
int add(int val) {
if (que.size() == k) {
que.push(val);
que.pop();
} else {
que.push(val);
}
return que.size() >= k ? que.top() : 0;
}
};
```
##### 2. 373. 查找和最小的K对数字
题目链接：[373. 查找和最小的K对数字](https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/)
**题目描述**：给定两个数组`nums1`和`nums2`，以及一个整数`k`，找到`nums1`和`nums2`中所有可能的数对`(x, y)`，其中`x`属于`nums1`，`y`属于`nums2`，并且使这些数对的和最小的前`k`个数对。
**示例**：
```cpp
输入：nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3
输出：[[1, 2], [1, 4], [1, 6]]
```
**思路**：为了解决这个问题，我们可以使用一个小顶堆来维护最小的`k`个数对。遍历两个数组中的每一个元素，将它们的和与对应的索引加入到堆中。最后堆中的元素即为所求。
**代码实现**：
```cpp
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
for (int i = 0; i < nums1.size(); ++i) {
for (int j = 0; j < nums2.size(); ++j) {
if (pq.size() < k) {
pq.push({nums1[i] + nums2[j], {nums1[i], nums2[j]}});
} else {
if (nums1[i] + nums2[j] < pq.top().first) {
pq.pop();
pq.push({nums1[i] + nums2[j], {nums1[i], nums2[j]}});
} else {
break;
}
}
}
}
vector<vector<int>> res;
while (!pq.empty()) {
res.push_back({pq.top().second.first, pq.top().second.second});
pq.pop();
}
return res;
}
```
通过以上分析，我们不仅学习了顶堆的基本概念和使用方法，还掌握了如何利用顶堆解决实际问题的方法。这些技能在面试和日常开发中都是非常有用的。
