सी ++ में अधिकतम ढेर में न्यूनतम तत्व।

समस्या कथन

अधिकतम ढेर में कम से कम मान वाला तत्व खोजें।

आइए हम अधिकतम ढेर के नीचे विचार करें।

रूट नोड के अधिकतम ढेर मूल्य में हमेशा उसके बच्चे से अधिक होता है। इस संपत्ति के कारण, हम यह निष्कर्ष निकाल सकते हैं कि मान लीफ नोड्स में से एक में मौजूद होगा। यदि ढेर में n नोड्स हैं तो छत (n/2) पत्ते होंगे।

मैक्स हीप एक पूर्ण बाइनरी ट्री है इसलिए इसे एक सरणी में दर्शाया जा सकता है। ऐसे ढेर में पहला पत्ता फ्लोर (n/2) इंडेक्स के बाद मौजूद होगा। तो हमारे उदाहरण में, पहली छुट्टी इंडेक्स 5 पर मौजूद होगी।

एल्गोरिदम

अधिकतम ढेर में न्यूनतम मान खोजने के लिए हम नीचे दिए गए एल्गोरिदम का उपयोग कर सकते हैं -

1. Find first leaf in a heap and consider its value as min
2. Iterate all remaining leaves and update min value if leaf with smaller value is found

उदाहरण

#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