C++怎么实现一个最小堆来解决Top K问题_C++算法面试与优先队列-C++-PHP中文网

C++怎么实现一个最小堆来解决Top K问题_C++算法面试与优先队列

穿越時空

发布： 2025-11-22 19:33:58

原创

259人浏览过

最小堆可在O(n log k)时间内求解Top K问题，通过维护大小为K的堆保留最大K个元素，C++中利用priority_queue并指定较小值优先的比较器实现最小堆，遍历数组时当堆未满直接插入，否则在当前元素大于堆顶时替换堆顶，最终堆顶即为第K大元素。

c++怎么实现一个最小堆来解决top k问题_c++算法面试与优先队列

在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大元素。

秘塔写作猫

秘塔写作猫是一个集AI写作、校对、润色、配图等为一体的创作平台

127

查看详情

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();
}