priority_queue<int, vector<int>, cmp> q的作用

时间: 2023-04-09 15:02:00 浏览: 114

C++之常见顶堆问题汇总

### 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; } ``` 通过以上分析，我们不仅学习了顶堆的基本概念和使用方法，还掌握了如何利用顶堆解决实际问题的方法。这些技能在面试和日常开发中都是非常有用的。

这个priority_queue是一个STL容器，它可以用来实现堆的数据结构，其中cmp是一个比较函数，用来指定元素的排序方式。在这个priority_queue中，元素的类型是int，排序方式是从大到小。

阅读全文

priority_queue<int, vector<int>, cmp> q的作用

相关推荐

手稿_V1.0114

关于C++中定义比较函数的三种方法小结

priority_queue<int, vector<int>, decltype(wait_priority_cmp)> wait_left(wait_priority_cmp)什么意思

priority_queue, vector>, decltype(cmp)> pq(cmp); 这是什么语法

priority_queue<int, vector<int>, cmp> pq; 这行代码中的vector<int>是干嘛的？

std::priority_queue<int, std::vector<int>, decltype(cmp)> minHeap(cmp);实现下cmp代码

解释下面每行代码struct cmp { bool operator()(int a,int b) { return dis[a]>dis[b]; } }; priority_queue<int,vector<int>,cmp> q;

std::priority_queue<int, std::vector<int>, decltype(cmp)> minHeap(cmp);这里的cmp可以换成max吗

auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) -> bool { return a.second < b.second; }; priority_queue, vector>, decltype(cmp)> que(cmp);

对于优先队列priority_queue, vector >, cmp>mine，该如何把数据加入该队列

reference to non-static member function must be called 7 | std::priority_queue<int, std::vector<int>, decltype(cmp2)> q(cmp2);

priority_queue怎么用cmp

priority_queue cmp为什么返回true

priority_queue 自定义比较

priority_queue 自定义lambda

priority_queue存struct

priority_queue如何自定义规则

最新推荐

spring 异步编程样例

火炬连体网络在MNIST的2D嵌入实现示例

管理建模和仿真的文件

L2正则化的终极指南：从入门到精通，揭秘机器学习中的性能优化技巧

如何构建一个符合GB/T19716和ISO/IEC13335标准的信息安全事件管理框架，并确保业务连续性规划的有效性？

Angular插件增强Application Insights JavaScript SDK功能

"互动学习：行动中的多样性与论文攻读经历"

L1正则化模型诊断指南：如何检查模型假设与识别异常值（诊断流程+案例研究）

如何构建一个符合GB/T19716和ISO/IEC13335标准的信息安全事件管理框架，并确保业务连续性规划的有效性？

实时三维重建：InfiniTAM的ros驱动应用