সমস্যা বিবরণ
ম্যাক্স হিপ-এ সবচেয়ে কম মান বিশিষ্ট এলিমেন্ট বের করো।
নিচের ম্যাক্স হিপটি বিবেচনা করো।
ম্যাক্স হিপ-এ রুট নোডের মান সবসময় এর চাইল্ড গুলোর চেয়ে বড় থাকে। এই প্রপার্টির কারণে, আমরা নিষ্কর্ষ করতে পারি যে মানটি লীফ নোড গুলোর একটি-এ থাকবে। যদি হিপ-এ nটি নোড থাকে তবে ceil(n/2)টি লীফ থাকবে।
ম্যাক্স হিপ একটি কমপ্লিট বাইনারি ট্রি তাই এটিকে অ্যারেতে রিপ্রেজেন্ট করা যায়। এমন হিপ-এ প্রথম লীফ floor(n/2) ইনডেক্সের পরে থাকবে। আমাদের উদাহরণে, প্রথম লীফ ইনডেক্স ৫-এ থাকবে।
অ্যালগরিদম
নিচের অ্যালগরিদম ব্যবহার করে ম্যাক্স হিপ-এ মিন ভ্যালু বের করা যায় -
1. হিপ-এ প্রথম লীফ খুঁজে বের করো এবং তার মানকে min হিসেবে বিবেচনা করো 2. বাকি সব লীফ গুলো ইটারেট করো এবং ছোট মান পাওয়া গেলে min ভ্যালু আপডেট করো
উদাহরণ (C++ কোড)
#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
