इंटरवल हीप्स से न्यूनतम तत्व हटाना

इंटरवल हीप से न्यूनतम तत्व हटाना

इंटरवल हीप में, **न्यूनतम तत्व हमेशा रूट नोड के लेफ्ट एंडपॉइंट पर होता है** (क्योंकि लेफ्ट एंडपॉइंट्स मिन-हीप बनाते हैं)।

चरण-दर-चरण प्रक्रिया

1. न्यूनतम एक्सेस करें: रूट के लेफ्ट एंडपॉइंट (`root.left`) को पुनः प्राप्त करें और लौटाएं।
2. रिक्ति बनाएं: रूट का लेफ्ट एंडपॉइंट अब खाली है।
3. अंतिम तत्व ले जाएं: अंतिम नोड से एक तत्व (प्राथमिकता लेफ्ट एंडपॉइंट) को हटाएं और इसे रूट के लेफ्ट पोजीशन पर रखें।
4. ट्रिकल-डाउन (रीइन्सर्ट): इस तत्व की तुलना नीचे जाने वाले पथ पर लेफ्ट एंडपॉइंट्स से करें, मिन-हीप गुण को पुनर्स्थापित करने के लिए छोटे बच्चों के साथ स्वैप करें।
5. क्रॉस-चेक: किसी भी बिंदु पर, यदि लेफ्ट एंडपॉइंट अपने नोड के राइट एंडपॉइंट से बड़ा हो जाता है (`left > right`), तो **उन्हें स्वैप करें** ताकि `left ≤ right` बना रहे, फिर तुलना जारी रखें।
6. समाप्ति: प्रक्रिया तब रुकती है जब मिन-हीप गुण और इंटरवल गुण दोनों संतुष्ट होते हैं।

विशेष मामले

• खाली हीप: `removeMin` विफल होता है / त्रुटि लौटाता है।
• एकल तत्व: वह तत्व लौटाएं, खाली हीप छोड़ दें।
• रूट अंतिम नोड है: लेफ्ट एंडपॉइंट हटाने के बाद, यदि नोड खाली हो जाता है, तो इसे हटा दें; कोई रीइन्सर्शन आवश्यक नहीं।

एल्गोरिदम सारांश

removeMin():
    if empty: fail
    if size == 1: return only_element; make empty

    min = root.left
    root.left = null

    if root is last node:
        if root.right exists: root.left = root.right; root.right = null
        return min

    // अंतिम नोड से लेफ्ट एंडपॉइंट लें
    p = last_node.left
    remove p from last_node
    if last_node becomes empty: remove last_node

    // p को मिन-हीप (लेफ्ट एंडपॉइंट्स) में रीइन्सर्ट करें
    reinsert_min(p, root)

    return min

जटिलता

• समय: **O(log n)** - ट्री की ऊंचाई।
• स्पेस: **O(1)** अतिरिक्त।