好资源导航 » 文章资讯 » C++ 中最大堆中的第 K 个最大元素

C++ 中最大堆中的第 K 个最大元素

2023-06-15 10:43:03 86

在本教程中，我们将编写一个程序，从最大堆中找到第k个最大的元素。

我们将使用优先队列来解决这个问题。让我们看看完成该程序的步骤。

用正确的值初始化最大堆。

创建优先队列并插入最大堆的根节点。

编写一个迭代k-1次的循环。

从队列中弹出最大的元素。

将上述节点的左右节点加入优先级队列。

优先级队列中最大的元素现在是第k个最大的元素。

把它返还。

示例

让我们看看代码。

#include 
using namespace std;
struct Heap {
   vector elemets;
   int n;
   Heap(int i = 0): n(i) {
      elemets = vector(n);
   }
};
inline int leftIndex(int i) {
   return 2 * i + 1;
}
inline int rightIndex(int i) {
   return 2 * i + 2;
}
int findKthGreatestElement(Heap &heap, int k) {
   priority_queue> queue;
   queue.push(make_pair(heap.elemets[0], 0));
   for (int i = 0; i < k - 1; ++i) {
      int node = queue.top().second;
      queue.pop();
      int left = leftIndex(node), right = rightIndex(node);
      if (left < heap.n) {
         queue.push(make_pair(heap.elemets[left], left));
      }
      if (right < heap.n) {
         queue.push(make_pair(heap.elemets[right], right));
      }
   }
   return queue.top().first;
}
int main() {
   Heap heap(10);
   heap.elemets = vector{ 44, 42, 35, 33, 31, 19, 27, 10, 26, 14 };
   cout << findKthGreatestElement(heap, 4) << endl;
   return 0;
}

输出结果

如果你运行上面的代码，那么你会得到下面的结果。

结论

如果您对本教程有任何疑问，请在评论部分提及。

返回顶部
514930285
czq8825@qq.com

C++ 中最大堆中的第 K 个最大元素

示例

结论

热门推荐

随机推荐