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