इंटरवल हीप्स में तत्व सम्मिलन

इंटरवल हीप में सम्मिलन

सम्मिलन तर्क इस बात पर निर्भर करता है कि वर्तमान तत्वों की संख्या **सम** है या **विषम**।

केस 1: विषम संख्या में तत्व (अंतिम नोड में एक तत्व है)

1. नया तत्व **अंतिम नोड** में दूसरे तत्व के रूप में डाला जाता है (अब नोड में `[a, b]` है)।
2. दोनों तत्वों को ऑर्डर करें: सुनिश्चित करें `left ≤ right`।
3. नए तत्व (अब लेफ्ट या राइट एंडपॉइंट) की तुलना उसके पैरेंट के संबंधित एंडपॉइंट से करें।
4. मिन-हीप (यदि लेफ्ट) या मैक्स-हीप (यदि राइट) के लिए मानक बबल-अप करें।
5. यदि किसी बिंदु पर `left > right`, उन्हें स्वैप करें और उपयुक्त हीप में बबल-अप जारी रखें।

केस 2: सम संख्या में तत्व (सभी नोड्स भरे हुए हैं)

1. एक **नया नोड** बनाएं (ट्री में अगली उपलब्ध पोजीशन)।
2. नए तत्व की तुलना उसके पैरेंट नोड के अंतराल `[p_left, p_right]` से करें:
   • यदि `new ≤ p_left` → **मिन-हीप** से संबंधित (नए नोड के लेफ्ट में रखें)।
   • यदि `new ≥ p_right` → **मैक्स-हीप** से संबंधित (नए नोड के राइट में रखें)।
   • यदि `p_left < new < p_right` → **पैरेंट के अंतराल के भीतर** आता है। इसे नए नोड में रखें (दोनों एंडपॉइंट्स के रूप में `[new, new]`) और **रुकें** - कोई बबल-अप आवश्यक नहीं।
3. यदि मिन/मैक्स हीप में रखा गया है, तो संबंधित हीप में बबल-अप करें।
4. बबल-अप के दौरान, यदि `left > right` हो जाता है, तो स्वैप करें और दूसरी हीप में जारी रखें।

समय जटिलता

• सबसे खराब स्थिति: **O(log n)** (रूट तक बबल-अप)।
• सबसे अच्छी स्थिति: **O(1)** (पैरेंट अंतराल के भीतर आता है, केस 2)।

मुख्य अंतर्दृष्टि

"पैरेंट अंतराल के भीतर" मामला (केस 2) इंटरवल हीप्स के लिए अद्वितीय है और सम्मिलन के लिए एक तेज़ रास्ता प्रदान करता है, जो औसत प्रदर्शन में सुधार करता है।