資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法律學C++ 中 Min 堆中的第 K 小元素
在本教程中，我們將編寫一個程式，從 min 堆中找到第 k 小的元素。
我們將使用優先順序佇列來解決這個問題。我們來看一下完成該程式的步驟。
- 用正確的值初始化 min 堆。
- 建立一個優先順序佇列，並插入 min 堆的根節點。
- 編寫一個迴圈，迭代 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>, vector<pair<int, int>>, greater<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>{ 10, 14, 19, 24, 32, 41, 27, 44, 35, 33 };
cout << findKthGreatestElement(heap, 4) << endl;
return 0;
}輸出
如果您執行以上程式碼，您將獲得以下結果。
24
結論
如果您對本教程有任何疑問，請在評論部分提及。
更新時間： 2021 年 4 月 9 日
475 次瀏覽
廣告