इंटरवल हीप प्रारंभिकरण
एक इंटरवल हीप एक पूर्ण बाइनरी ट्री है जहां प्रत्येक नोड (संभवतः अंतिम को छोड़कर) एक अंतराल `[a, b]` संग्रहीत करता है जहां `a ≤ b`।
गुण
- लेफ्ट एंडपॉइंट्स (`a` मान) एक **मिन-हीप** बनाते हैं।
- राइट एंडपॉइंट्स (`b` मान) एक **मैक्स-हीप** बनाते हैं।
- किसी भी नॉन-रूट नोड का अंतराल उसके पैरेंट के अंतराल का **सब-इंटरवल** होता है: `parent.a ≤ node.a ≤ node.b ≤ parent.b`।
- यदि तत्वों की संख्या विषम है, तो अंतिम नोड में एक ही तत्व होता है (दोनों एंडपॉइंट्स के रूप में माना जाता है)।
प्रारंभिकरण एल्गोरिदम (बॉटम-अप हीपिफाई)
मानक हीप बिल्डिंग की तरह, हम अंतिम आंतरिक नोड से रूट तक जाते हैं। प्रत्येक सबट्री रूट के लिए:
- रूट ऑर्डर करें: सुनिश्चित करें `left ≤ right`। यदि नहीं, तो उन्हें स्वैप करें।
- लेफ्ट एंडपॉइंट को मिन-हीप में पुनः डालें: `removeMin` के लिए उपयोग की जाने वाली समान रीइन्सर्शन रणनीति का उपयोग करके लेफ्ट एंडपॉइंट को मिन-हीप में नीचे ले जाएं।
- राइट एंडपॉइंट को मैक्स-हीप में पुनः डालें: `removeMax` रणनीति का उपयोग करके राइट एंडपॉइंट को मैक्स-हीप में नीचे ले जाएं।
विषम तत्वों का संचालन
- सम संख्या: प्रत्येक नोड में दो तत्व `[a, b]` होते हैं।
- विषम संख्या: अंतिम नोड में एक तत्व `[c, c]` होता है (एकल तत्व अंतराल)।
जटिलता
- समय: **O(n)** - मानक फ्लॉयड के हीप बिल्ड के समान, प्रत्येक नोड पर O(ऊंचाई) कार्य।
- स्पेस: **O(n)** - सरणी-आधारित निहित प्रतिनिधित्व।
उदाहरण अंतर्ज्ञान
एक सरणी प्रतिनिधित्व में इंडेक्स i पर नोड के लिए:
- लेफ्ट चाइल्ड: `2i`, राइट चाइल्ड: `2i+1`।
- लेफ्ट एंडपॉइंट इंडेक्स `2i` (या सरणी ऑफसेट) पर संग्रहीत।
- राइट एंडपॉइंट इंडेक्स `2i+1` पर संग्रहीत।
- हीपिफाई लूप: `for (i = n/2; i >= 1; i--) heapify_subtree(i);`
