इस ट्यूटोरियल में, हम k-th . खोजने जा रहे हैं प्रत्येक प्रविष्टि के बाद सबसे छोटा तत्व।
हम समस्या को हल करने के लिए मिन-हीप का उपयोग करने जा रहे हैं। आइए कार्यक्रम को पूरा करने के चरणों को देखें।
- यादृच्छिक डेटा के साथ सरणी प्रारंभ करें।
- प्राथमिकता कतार प्रारंभ करें।
- k - 1 तक कोई k-th नहीं होगा सबसे छोटा तत्व। इसलिए, अपनी पसंद का कोई भी प्रतीक प्रिंट करें।
- एक लूप लिखें जो k + 1 से n तक पुनरावृत्त हो।
- मिन-हीप की जड़ प्रिंट करें।
- अगर एलिमेंट मिन-हीप के रूट से बड़ा है, तो रूट को पॉप करें और एलीमेंट डालें।
उदाहरण
आइए कोड देखें।
#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
निष्कर्ष
यदि ट्यूटोरियल में आपके कोई प्रश्न हैं, तो उनका टिप्पणी अनुभाग में उल्लेख करें।