हीप (Heap) एक विशेष तरह का ट्री डेटा स्ट्रक्चर है जो हीप प्रॉपर्टी (heap property) का पालन करता है:
🗼
यदि P किसी C का पेरेंट नोड है, तो मैक्स-हीप (max-heap) में P का मान C से बड़ा या उसके बराबर होना चाहिए, और मिन-हीप (min-heap) में P का मान C से छोटा या उसके बराबर होना चाहिए।
8 नोड वाले एक मैक्स-हीप का उदाहरण
हीप मुख्य तौर पर दो प्रकार की होती हैं:
मैक्स हीप (Max Heap): पेरेंट नोड का मान अपने चाइल्ड नोड्स से बड़ा या बराबर होना चाहिए।
मिन हीप (Min Heap): पेरेंट नोड का मान अपने चाइल्ड नोड्स से छोटा या बराबर होना चाहिए।
हम मैक्स-हीप पर ध्यान केंद्रित करेंगे, क्योंकि ज़्यादातर स्टैंडर्ड लाइब्रेरीज़ में प्रायोरिटी क्यू (priority queue) के लिए मैक्स-हीप ही लागू की जाती है। मैक्स-हीप में ट्री की रूट (root) सबसे बड़ा एलिमेंट होता है, जबकि पत्तियाँ (leaves) सबसे छोटी होती हैं। लेकिन पत्तियों के बीच किसी विशेष क्रम की गारंटी नहीं होती। इसलिए सिर्फ यह निश्चित होता है कि रूट नोड सबसे बड़ा है और उसके चाइल्ड नोड्स का मान रूट से छोटा या उसके बराबर होना चाहिए।
ध्यान दें कि हीप की अंतिम पंक्ति (last row) हमेशा बाएँ से दाएँ भरी जाती है। यानी पहले बाएँ ओर का लीफ़ भरा जाता है और अंत में दाएँ ओर का लीफ़ — जैसा कि ऊपर की तस्वीर में दिखाया गया है।
Implementation
हीप को एक ऐरे (array) के रूप में लागू किया जा सकता है, जहाँ ऐरे का पहला एलिमेंट रूट नोड का प्रतिनिधित्व करता है। क्योंकि प्रत्येक नोड के केवल दो चाइल्ड होते हैं, हम इंडेक्सिंग कुछ इस तरह से कर सकते हैं:
रूट एलिमेंट का इंडेक्स 1 होता है।
बाएँ और दाएँ चाइल्ड क्रमशः 2i और 2i+1 पर होते हैं।
इंडेक्स i वाले किसी एलिमेंट का पेरेंट नोड i // 2 पर स्थित होता है।
ऊपर दिए हीप को एक लिस्ट में इस तरह लिखा जा सकता है:
# तस्वीर में दिखाए गए प्रत्येक लेवल को पढ़कर संख्या को क्रम से लिखें
heap = [None, 8, 5, 7, 1, 1, 6, 3, 1]
# या इसे थोड़ा दर्शनीय ढंग से देखने के लिए
heap = [None, # हम [0] इंडेक्स को छोड़ देते हैं ताकि इंडेक्सिंग सरल रहे
8, # इंडेक्स [1]
5, 7, # इंडेक्स [2, 3]
1, 1, 6, 3, # इंडेक्स [4, 5, 6, 7]
1] # इंडेक्स [8]
Challenge: Check if the binary tree is a heap
मान लीजिए कि आपको एक बाइनरी ट्री (binary tree) दिया गया है, जो एक ऐरे में n संख्याओं के रूप में संग्रहित है (ऊपर वर्णित इंडेक्सिंग के अनुसार)। आपका काम यह जाँचना है कि यह मैक्स-हीप प्रॉपर्टी का पालन करता है या नहीं।
Input
इनपुट की पहली पंक्ति में एक अकेला पूर्णांक n होता है (1 ≤ n ≤ 100 000)।
अगली पंक्ति में n स्पेस-सेपरेटेड इन्टीजर दिए गए हैं (), जो हीप के एलिमेंट्स की वैल्यूज़ का प्रतिनिधित्व करते हैं।
Output
यदि इनपुट में दिया गया बाइनरी ट्री मैक्स-हीप प्रॉपर्टी पूरा करता है, तो प्रोग्राम को Yes प्रिंट करना चाहिए, अन्यथा No।
Examples
इनपुट
आउटपुट
8
8 5 7 1 1 6 3 1
Yes
7
8 5 7 1 9 6 3
No
Explanation
उदाहरण 1
All the parent nodes have a value larger than or equal to their child nodes. Therefore, the heap property is satisfied.
उदाहरण 2
The node with a value of 9 is larger than its parent node. Therefore, the heap property is not satisfied.
