डिएप्स (Deaps) से न्यूनतम तत्व हटाना

डिएप में न्यूनतम तत्व का विलोपन

डिएप (Deap) एक डबल-एंडेड हीप संरचना है जहां लेफ्ट सबट्री मिन-हीप है और राइट सबट्री मैक्स-हीप है। रूट खाली होता है। न्यूनतम तत्व मिन-हीप (लेफ्ट सबट्री) की रूट पर होता है।

विलोपन एल्गोरिदम

चूंकि ट्री की ऊंचाई हमेशा log n होती है, विलोपन O(log n) समय लेता है।

Procedure deap_deletion(b[], m):
    if (m < 2) return;           // कोई तत्व नहीं
    min = b[2];                  // न्यूनतम मान सहेजें (इंडेक्स 2 पर)

    // मिन-हीप में नीचे जाएं, बच्चों में से छोटे को ऊपर लाएं
    for (i = 2; 2*i <= m; b[i] = b[k], i = k) {
        k = i * 2;               // लेफ्ट चाइल्ड
        if (k+1 <= m && b[k] > b[k+1])
            k++;                 // राइट चाइल्ड छोटा है
    }

    // अब i एक लीफ स्थिति पर है। मैक्स-हीप से कॉरेस्पॉन्डिंग नोड खोजें
    k = max_value(i);

    if (x > b[k]) {              // x अंतिम तत्व है जिसे पुनः डाला जा रहा है
        b[i] = b[k];
        insert x into maximum subtree;
    } else {
        insert x into minimum subtree;
    }

व्याख्या

1. न्यूनतम तत्व `b[2]` पर होता है (क्योंकि `b[1]` रूट है और खाली है)।
2. मानक हीप विलोपन की तरह, हम लेफ्ट सबट्री (मिन-हीप) में नीचे जाते हैं, प्रत्येक स्तर पर छोटे बच्चे को ऊपर लाते हैं।
3. जब हम एक लीफ पर पहुँचते हैं, तो हम मैक्स-हीप में इसके कॉरेस्पॉन्डिंग नोड को `max_value(i)` का उपयोग करके ढूंढते हैं।
4. अंतिम तत्व (`x`) को उपयुक्त सबट्री में पुनः डाला जाता है ताकि डिएप गुण बने रहें।

मुख्य बिंदु

• समय जटिलता: O(log n)।
• कॉरेस्पॉन्डेंस `max_value`/`min_value` फ़ंक्शन्स द्वारा बनाए रखा जाता है।
• यह प्रक्रिया डुअल-हीप कॉरेस्पॉन्डेंस विधि का एक विशिष्ट कार्यान्वयन है।