C++ 中最大堆中的第 K 个最大元素
在本教程中,我们将编写一个程序,从最大堆中找到第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; }
如果你运行上面的代码,那么你会得到下面的结果。
33
结论
如果您对本教程有任何疑问,请在评论部分提及。
热门推荐
1 训练狗狗憋尿
2 狗狗追踪训练
3 狗狗训练要多少钱
5 深圳狗狗训练
6 训练狗狗唤回
7 狗狗叫怎么训练
8 狗狗训练班
10 狗狗社会化训练
11 狗狗叫回训练
12 广州狗狗训练学校
13 狗狗训练躺下
14 狗狗随行训练
15 训练狗狗巡回
16 狗狗要怎么训练
17 狗狗喂食训练
18 训练狗狗躺下