हीप डेटा स्ट्रक्चर

हीप संतुलित बाइनरी ट्री डेटा संरचना का एक विशेष मामला है जहां रूट-नोड कुंजी की तुलना उसके बच्चों के साथ की जाती है और उसी के अनुसार व्यवस्थित की जाती है। अगरα बच्चे का नोड है β तब -

कुंजी (α) (कुंजी (≥)

चूंकि माता-पिता का मूल्य बच्चे की तुलना में अधिक है, इसलिए यह संपत्ति उत्पन्न करता है Max Heap। इस मापदंड के आधार पर, ढेर दो प्रकार के हो सकते हैं -

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap - जहाँ रूट नोड का मान उसके किसी भी बच्चे से कम या उसके बराबर है।

Max-Heap - जहां रूट नोड का मूल्य उसके किसी भी बच्चे से अधिक या उसके बराबर है।

दोनों पेड़ों का निर्माण एक ही इनपुट और आगमन के आदेश का उपयोग करके किया जाता है।

मैक्स हीप कंस्ट्रक्शन एलगोरिदम

हम एक ही उदाहरण का उपयोग करके दिखा सकते हैं कि मैक्स हीप कैसे बनाया जाता है। मिन हीप बनाने की प्रक्रिया समान है लेकिन हम अधिकतम मूल्यों के बजाय न्यूनतम मूल्यों के लिए जाते हैं।

हम एक बार में एक तत्व डालकर अधिकतम ढेर के लिए एक एल्गोरिथ्म प्राप्त करने जा रहे हैं। किसी भी समय, ढेर को अपनी संपत्ति बनाए रखना चाहिए। सम्मिलन करते समय, हम यह भी मानते हैं कि हम पहले से ही लगाए गए पेड़ में एक नोड डाल रहे हैं।

Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Note - मिन हीप निर्माण एल्गोरिथ्म में, हम बच्चे के नोड की तुलना में मूल नोड के मूल्य की अपेक्षा करते हैं।

आइए एक एनिमेटेड चित्रण द्वारा मैक्स हीप निर्माण को समझें। हम उसी इनपुट नमूने पर विचार करते हैं जिसका उपयोग हमने पहले किया था।

मैक्स हीप डिलेक्शन एल्गोरिथ्म

हमें अधिकतम हीप से हटाने के लिए एक एल्गोरिथ्म प्राप्त करें। अधिकतम (या न्यूनतम) हीप में हमेशा अधिकतम (या न्यूनतम) मान निकालने के लिए मूल में होता है।

Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.