समस्या कथन
मैक्स हीप में सबसे कम मान वाला एलिमेंट ढूंढें।
नीचे दिए गए मैक्स हीप पर विचार करें।
मैक्स हीप में रूट नोड का मान हमेशा उसके बच्चों से अधिक होता है। इस गुण के कारण, हम निष्कर्ष निकाल सकते हैं कि मान लीफ नोड्स में से एक में मौजूद होगा। यदि हीप में n नोड्स हैं तो ceil(n/2) लीफ होंगे।
मैक्स हीप एक पूर्ण बाइनरी ट्री है इसलिए इसे ऐरे में दर्शाया जा सकता है। ऐसे हीप में पहला लीफ floor(n/2) इंडेक्स के बाद मौजूद होगा। इसलिए हमारे उदाहरण में, पहला लीफ इंडेक्स 5 पर मौजूद होगा।
एल्गोरिदम
हम मैक्स हीप में न्यूनतम मान खोजने के लिए नीचे दिए गए एल्गोरिदम का उपयोग कर सकते हैं -
1. हीप में पहला लीफ ढूंढें और उसके मान को min मानें 2. सभी शेष लीफ्स पर इटरेट करें और यदि छोटे मान वाला लीफ मिले तो min वैल्यू अपडेट करें
उदाहरण
#include <iostream> #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) using namespace std; int getMinElement(int *heap, int n){ int minElement = heap[n / 2]; for (int i = n / 2 + 1; i < n; ++i) { minElement = min(minElement, heap[i]); } return minElement; } int main(){ int heap[] = {120, 90, 100, 70, 75, 80, 60, 25, 40, 35}; cout << "Min value: " << getMinElement(heap, SIZE(heap)) << "\n"; return 0; }आउटपुट
जब आप उपरोक्त प्रोग्राम को कंपाइल और एक्जीक्यूट करते हैं। यह निम्नलिखित आउटपुट जनरेट करता है -
Min value: 25
