最小堆可在O(n log k)时间内求解Top K问题，通过维护大小为K的堆保留最大K个元素，C++中利用priority_queue并指定较小值优先的比较器实现最小堆，遍历数组时当堆未满直接插入，否则在当前元素大于堆顶时替换堆顶，最终堆顶即为第K大元素。
在C++中解决Top K问题，最小堆是一种高效的方法，尤其当数据量大、K值相对较小的时候。使用最小堆可以在O(n log k)的时间复杂度内找出最大的K个元素，比排序整个数组更高效。
最小堆的基本实现
最小堆是一个完全二叉树，父节点的值小于等于子节点。可以用一个vector来模拟堆结构，通过索引关系维护父子节点：
父节点索引：(i – 1) / 2左子节点索引：2 * i + 1右子节点索引：2 * i + 2
核心操作包括插入（上浮）和删除堆顶（下沉）：
void push(int val) { heap.push_back(val); shiftUp(heap.size() – 1); }
void pop() { if (!heap.empty()) { swap(heap[0], heap.back()); heap.pop_back(); shiftDown(0); } }
用最小堆解决Top K最大元素
维护一个大小为K的最小堆，遍历数组时：
立即学习“C++免费学习笔记（深入）”；
如果堆未满，直接插入元素如果堆已满且当前元素大于堆顶，替换堆顶并调整
这样最终堆中保存的就是最大的K个数，堆顶是其中最小的，即第K大元素。
int findKthLargest(vector& nums, int k) {
priority_queue, greater> minHeap;
for (int num : nums) {
if (minHeap.size()
minHeap.push(num);
} else if (num > minHeap.top()) {
minHeap.pop();
minHeap.push(num);
}
}
return minHeap.top();
}
C++标准库中的优先队列
C++提供了priority_queue，默认是最大堆。要创建最小堆，需指定比较函数：
priority_queue, greater> minHeap;
常用接口：
push(x)：插入元素pop()：删除堆顶top()：访问堆顶size()：获取堆大小
利用这些接口，可以快速实现Top K逻辑，避免手动实现堆操作。
基本上就这些。用最小堆处理Top K问题，关键是控制堆大小为K，只保留较大的元素。结合priority_queue能大幅简化代码，适合面试场景。注意比较器的选择，别把最大堆和最小堆搞反了。
以上就是C++怎么实现一个最小堆来解决Top K问题_C++算法面试与优先队列的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1485542.html
微信扫一扫 
支付宝扫一扫 
