এই টিউটোরিয়ালে, আমরা একটি প্রোগ্রাম লিখব যা ম্যাক্স-হিপ (max-heap) থেকে K-তম সর্বোচ্চ উপাদান বের করবে।
এই সমস্যাটি সমাধানের জন্য আমরা প্রায়োরিটি কিউ (priority queue) ব্যবহার করব। প্রোগ্রাম সম্পন্ন করার ধাপগুলো নিচে দেওয়া হলো:
সমস্যা সমাধানের ধাপসমূহ
- সঠিক মান দিয়ে ম্যাক্স-হিপ ইনিশিয়ালাইজ করুন।
- একটি প্রায়োরিটি কিউ তৈরি করুন এবং ম্যাক্স-হিপের রুট নোডটি ইনসার্ট করুন।
- k-1 বার ইটারেট করার একটি লুপ চালান।
- কিউ থেকে সর্বোচ্চ উপাদানটি পপ (pop) করুন।
- উপরোক্ত নোডের বাম (left) এবং ডান (right) নোডগুলো প্রায়োরিটি কিউতে ইনসার্ট করুন।
- প্রায়োরিটি কিউতে সর্বোচ্চ উপাদানটি এখন 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
নিষ্কর্ষ
এই টিউটোরিয়াল সম্পর্কে আপনার যেকোনো প্রশ্ন থাকলে কমেন্ট সেকশনে জানাতে পারেন।
