Trong hướng dẫn này, chúng ta sẽ viết một chương trình tìm phần tử thứ k nhỏ nhất từ min-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 min-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 min-heap.
- Viết một vòng lặp lặp lại k - 1 lần.
- Đưa ra phần tử ít nhất từ 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>, 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;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
24
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.