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

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

2023-06-21 20:15:03 77

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

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

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

创建一个优先级队列并插入min-heap的根节点。

编写一个循环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, vector>, greater>>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{ 10, 14, 19, 24, 32, 41, 27, 44, 35, 33 };
   cout << findKthGreatestElement(heap, 4) << endl;
   return 0;
}

输出结果

如果运行上面的代码，则将得到以下结果。

返回顶部
514930285
czq8825@qq.com

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

示例

热门推荐

随机推荐