数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中最大堆中的第 K 大元素
在本教程中，我们将编写一个程序，该程序会从最大堆中找出第 K个最大元素。
我们将使用优先级队列来解决这个问题。让我们了解完成此程序所需的步骤。
- 以正确的值初始化最大堆。
- 创建一个优先级队列并插入最大堆的根节点。
- 编写一个循环，重复 K - 1 次。
- 从队列中弹出最大的元素。
- 将上述节点的左节点和右节点添加到优先级队列中。
- 优先级队列中的最大元素现在是第 K 个最大元素。
- 返回它。
示例
让我们看看代码。
#include <bits/stdc++.h>
using namespace std;
struct Heap {
vector<int> elemets;
int n;
Heap(int i = 0): n(i) {
elemets = vector<int>(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<pair<int, int>> 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<int>{ 44, 42, 35, 33, 31, 19, 27, 10, 26, 14 };
cout << findKthGreatestElement(heap, 4) << endl;
return 0;
}输出
如果运行以上代码，那么你将得到以下结果。
33
结论
如果你对本教程有任何疑问，请在评论部分中提及。
更新于：09-4-2021
1 千余浏览量
广告