এই টিউটোরিয়ালে, আমরা প্রতিটি ইনসারশনের পর K-তম সর্বনিম্ন উপাদান বের করব।
এই সমস্যাটি সমাধানের জন্য আমরা মিন-হিপ (min-heap) ব্যবহার করব। প্রোগ্রাম সম্পন্ন করার ধাপগুলো নিচে দেওয়া হলো:
সমস্যা সমাধানের ধাপসমূহ
- অ্যারের র্যান্ডম ডেটা ইনিশিয়ালাইজ করুন।
- প্রায়োরিটি কিউ (priority queue) ইনিশিয়ালাইজ করুন।
- K-1 পর্যন্ত কোনো K-তম সর্বনিম্ন উপাদান থাকবে না। তাই আপনার পছন্দের যেকোনো সিম্বল প্রিন্ট করুন।
- K+1 থেকে n পর্যন্ত একটি লুপ চালান।
- মিন-হিপের রুট (root) প্রিন্ট করুন।
- যদি উপাদানটি মিন-হিপের রুটের চেয়ে বড় হয়, তবে রুটটি পপ করে নতুন উপাদানটি ইনসার্ট করুন।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
void findKthSmallestElement(int elements[], int n, int k) {
priority_queue<int, vector<int>, greater<int>> queue;
for (int i = 0; i < k - 1; i++) {
queue.push(elements[i]);
cout << "- ";
}
queue.push(elements[k-1]);
for (int i = k; i < n; i++) {
cout << queue.top() << " ";
if (elements[i] > queue.top()) {
queue.pop();
queue.push(elements[i]);
}
}
cout << queue.top() << endl;
}
int main() {
int arr[] = {3, 5, 6, 2, 7, 8, 2, 3, 5, 9};
findKthSmallestElement(arr, 10, 5);
return 0;
}
আউটপুট
উপরের কোডটি রান করলে নিচের ফলাফল পাওয়া যাবে:
- - - - 2 3 3 3 5 5
নিষ্কর্ষ
এই টিউটোরিয়াল সম্পর্কে আপনার যেকোনো প্রশ্ন থাকলে কমেন্ট সেকশনে জানাতে পারেন।
