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