Trong hướng dẫn này, chúng tôi sẽ viết một chương trình tìm k-th phần tử lớn nhất từ max-heap.
Chúng tôi sẽ sử dụng hàng đợi ưu tiên để giải quyết vấn đề. Hãy xem các bước để hoàn thành chương trình.
- Khởi tạo max-heap với các giá trị chính xác.
- Tạo hàng đợi ưu tiên và chèn nút gốc của khối tối đa.
- Viết một vòng lặp lặp lại k - 1 lần.
- Đưa phần tử lớn nhất vào hàng đợi.
- Thêm các nút bên trái và bên phải của nút trên vào hàng đợi ưu tiên.
- Phần tử lớn nhất trong hàng đợi ưu tiên hiện là phần tử lớn nhất thứ k.
- Trả lại.
Ví dụ
Hãy xem mã.
#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;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
33
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.