C++ में मिन हीप में मान x से छोटे सभी नोड्स प्रिंट करना

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