C++ STL-এ হিপ: make_heap, push_heap, pop_heap, sort_heap, is_heap, is_heap_until

इस खंड में हम C++ STL में मौजूद हिप डेटा संरचना देखेंगे। यह हिप में तेजी से इनपुट की अनुमति देता है और एक नंबर की पुनर्प्राप्ति हमेशा सबसे बड़ी संख्या का परिणाम देती है यानी शेष संख्याओं में से सबसे बड़ी संख्या हर बार पॉप आउट होती है। हिप के अन्य तत्व कार्यान्वयन पर निर्भर करते हुए व्यवस्थित होते हैं। हिप ऑपरेशन निम्नलिखित हैं:

• make_heap() - यह एक कंटेनर में एक रेंज को हिप में बदल देता है।
• front() - यह हिप का पहला तत्व लौटाता है जो सबसे बड़ी संख्या है।

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include 
using namespace std;
int main() {
    vector heap = {33, 43, 53, 38, 28};
    make_heap(heap.begin(), heap.end());
    cout << "Top element is : " << heap.front() << endl;
}

आउटपुट

Top element is : 53

• push_heap() - यह हिप में एक तत्व डालने के बाद हिप को फिर से हिपिफाई करने में मदद करता है। हिप का आकार 1 से बढ़ जाता है। हिप में, नया तत्व उचित स्थान पर रखा जाता है।
• pop_heap() - यह हिप के सबसे बड़े तत्व को हटाने के बाद हिप को फिर से हिपिफाई करने में मदद करता है। हिप का आकार 1 से घट जाता है। एक तत्व को हटाने के बाद, हिप तत्वों को तदनुसार पुनर्गठित किया जाता है।

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include 
using namespace std;
int main() {
    vector heap = {33, 43, 53, 38, 28};
    make_heap(heap.begin(), heap.end());
    cout << "Top element is : " << heap.front() << endl;
    heap.push_back(60);
    push_heap(heap.begin(), heap.end());
    cout << "Top element after insert : " << heap.front() << endl;
    pop_heap(heap.begin(), heap.end());
    heap.pop_back();
    cout << "Top element after deletion : " << heap.front() << endl;
}

आउटपुट

Top element is : 53
Top element after insert : 60
Top element after deletion : 53

• sort_heap() - यह हिपसॉर्टिंग तकनीक द्वारा हिप तत्वों को आरोही क्रम में सॉर्ट करता है।

उदाहरण (C++)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include 
using namespace std;
int main() {
    vector heap = {33, 43, 53, 38, 28};
    make_heap(heap.begin(), heap.end());
    cout << "Before Sort : ";
    for (const auto &i : heap) {
        cout << i << ' ';
    }
    sort_heap(heap.begin(), heap.end());
    cout << "\nAfter Sort : ";
    for (const auto &i : heap) {
        cout << i << ' ';
    }
}

आउटपुट

Before Sort : 53 43 33 38 28
After Sort : 28 33 38 43 53

• is_heap() - यह जांचने के लिए उपयोग किया जाता है कि कंटेनर हिप है या नहीं। अधिकांश कार्यान्वयनों में, रिवर्स सॉर्टेड कंटेनर को हिप माना जाता है। यह फंक्शन true लौटाता है जब यह हिप होता है, अन्यथा false।
• is_heap_until() - यह उस स्थिति तक इटरेटर ढूंढने के लिए उपयोग किया जाता है जहां तक कंटेनर हिप है।

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include 
using namespace std;
int main() {
    vector heap = {33, 43, 53, 38, 28};
    vector::iterator iter;
    is_heap(heap.begin(), heap.end()) ? cout << "The is a heap " : cout << "The is not a heap";
    cout << endl;
    cout << "Heapify" << endl;
    make_heap(heap.begin(), heap.end());
    is_heap(heap.begin(), heap.end()) ? cout << "The is a heap " : cout << "The is not a heap";
    cout << endl;
    vector::iterator iter2 = is_heap_until(heap.begin(), heap.end());
    cout << "The heap elements are : ";
    for (iter = heap.begin(); iter != iter2; iter++)
        cout << *iter << " ";
}

आउटपुट

The is not a heap
Heapify
The is a heap
The heap elements are : 53 43 33 38 28