এই সমস্যায়, আমাদের একটি মিনিট হিপ দেওয়া হয়েছে এবং একটি মান x এবং আমাদের x এর চেয়ে কম সব নোড প্রিন্ট করতে হবে।
মিনিট হিপ একটি বিশেষ ধরনের বাইনারি ট্রি যেখানে প্রতিটি নোডের মান তার চাইল্ড নোডের নোড মানের থেকে কম থাকে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক -
X =45
আউটপুট - 2 4 7 10 17 22 33 34
এখন, এই সমস্যাটি সমাধান করার জন্য আমাদের পুরো মিন-হিপের প্রি-অর্ডার ট্রাভার্সাল করতে হবে এবং শুধুমাত্র সেই মানগুলি প্রিন্ট করতে হবে যেগুলি প্রদত্ত মানের X-এর চেয়ে কম। যদি একটি নোডের মান x এর থেকে বেশি হয়, তাহলে আমরা অতিক্রম করব না। চাইল্ড নোডের মান x এর চেয়ে বেশি হবে। আমরা মিন-হ্যাপের প্রি-অর্ডার ট্রাভার্সাল করার জন্য পুনরাবৃত্তি ব্যবহার করব।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
class MinHeap {
int* harr;
int capacity;
int heap_size;
public:
MinHeap(int capacity);
void Heapify(int);
int parent(int i) { return (i - 1) / 2; }
int left(int i) { return (2 * i + 1); }
int right(int i) { return (2 * i + 2); }
void insert(int k);
void printSmallerNodes(int k, int pos);
};
void MinHeap::printSmallerNodes(int x, int pos = 0){
if (pos >= heap_size)
return;
if (harr[pos] >= x) {
return;
}
cout<<harr[pos]<<" ";
printSmallerNodes(x, left(pos));
printSmallerNodes(x, right(pos));
}
MinHeap::MinHeap(int cap) {
heap_size = 0;
capacity = cap;
harr = new int[cap];
}
void MinHeap::insert(int k) {
if (heap_size == capacity) {
cout << "\nOverflow! Size Full\n";
return;
}
heap_size++;
int i = heap_size - 1;
harr[i] = k;
while (i != 0 && harr[parent(i)] > harr[i]) {
swap(harr[i], harr[parent(i)]);
i = parent(i);
}
}
void MinHeap::Heapify(int i) {
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i) {
swap(harr[i], harr[smallest]);
Heapify(smallest);
}
}
int main() {
MinHeap h(50);
h.insert(2);
h.insert(4);
h.insert(7);
h.insert(34);
h.insert(52);
h.insert(33);
h.insert(10);
h.insert(51);
h.insert(75);
h.insert(17);
h.insert(22);
int x = 45;
cout<<"All nodes with value smaller than "<<x<<" are\n";
h.printSmallerNodes(x);
return 0;
} আউটপুট
All nodes with a value smaller than 45 are 2 4 34 17 22 7 33 10
