इस समस्या में, हमें एक मिनी हीप दिया जाता है और एक मान 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. हैं