यादृच्छिक मेल्डेबल हीप

कंप्यूटर विज्ञान में, एक यादृच्छिक मेल्डेबल हीप (मेल्डेबल हीप (डेटा संरचना) या रैंडमाइज्ड मेल्डेबल प्राथमिकता कतार) एक प्राथमिकता कतार आधारित डेटा संरचना है जिसमें अंतर्निहित संरचना भी एक हीप-ऑर्डर द्विआधारी वृक्ष है। हालाँकि, अंतर्निहित बाइनरी ट्री के आकार पर कोई प्रतिबंध नहीं है।

समान डेटा संरचनाओं की तुलना में इस दृष्टिकोण के कई फायदे हैं। यह अधिक सरलता प्रदान करता है: यादृच्छिक मेल्डेबल ढेर के लिए सभी ऑपरेशन लागू करना आसान है और उनकी जटिलता सीमा में निरंतर कारक छोटे हैं। संतुलन स्थितियों को संरक्षित करने की भी कोई आवश्यकता नहीं है और नोड्स के भीतर कोई उपग्रह जानकारी आवश्यक नहीं है। अंत में, इस संरचना में सबसे खराब स्थिति में भी अच्छी समय दक्षता है। प्रत्येक व्यक्तिगत ऑपरेशन का निष्पादन समय उच्च संभावना के साथ अधिकतम लघुगणकीय होता है।

संचालन

रैंडमाइज्ड मेल्डेबल हीप कई सामान्य ऑपरेशनों का समर्थन करता है। ये सम्मिलन, विलोपन और एक खोज ऑपरेशन, फाइंडमिन हैं। सम्मिलन और विलोपन संचालन को मेल्डेबल हीप, मेल्ड (क्यू1, क्यू2) के लिए विशिष्ट एक अतिरिक्त ऑपरेशन के संदर्भ में कार्यान्वित किया जाता है।

मेल्ड

मेल्ड (जिसे मर्ज भी कहा जाता है) ऑपरेशन का मूल लक्ष्य दो हीप्स (प्रत्येक हीप्स रूट नोड्स लेकर), Q1 और Q2 लेना है, और उन्हें मर्ज करना है, जिसके परिणामस्वरूप एक ही हीप नोड वापस आता है। यह हीप नोड एक हीप का रूट नोड है जिसमें Q1 और Q2 पर आधारित दो उपवृक्षों के सभी तत्व शामिल हैं।

इस मेल्ड ऑपरेशन की एक अच्छी विशेषता यह है कि इसे पुनरावर्ती रूप से परिभाषित किया जा सकता है। यदि कोई भी ढेर शून्य है, तो विलय एक खाली सेट के साथ हो रहा है और विधि केवल गैर-खाली ढेर का रूट नोड लौटाती है। यदि Q1 और Q2 दोनों शून्य नहीं हैं, तो जांचें कि Q1 > Q2 है या नहीं। यदि ऐसा है, तो दोनों की अदला-बदली करें। इसलिए यह सुनिश्चित किया जाता है कि Q1 < Q2 और मर्ज किए गए ढेर के रूट नोड में Q1 होगा। फिर हम पुनरावर्ती रूप से Q2 को Q1.left या Q1.right के साथ मर्ज करते हैं। यह चरण वह है जहां यादृच्छिकरण आता है क्योंकि किस पक्ष के साथ विलय करना है इसका निर्णय सिक्का उछालकर निर्धारित किया जाता है।

फ़ंक्शन मेल्ड (नोड Q1, नोड Q2)
    यदि Q1 शून्य है => Q2 लौटाएँ
    यदि Q2 शून्य है => Q1 लौटाएँ
    यदि Q1 > Q2 => Q1 और Q2 को स्वैप करें
    यदि coin_toss 0 है => Q1.left = Meld(Q1.left, Q2)
    अन्यथा क्यू1.दाएं = मेल्ड(क्यू1.दाएं, क्यू2)
    वापसी Q1

सम्मिलित करें

मेल्ड ऑपरेशन पूरा होने पर, मेल्डेबल ढेर में डालना आसान है। सबसे पहले, एक नया नोड, यू, बनाया जाता है जिसमें मान x होता है। फिर इस नए नोड को हीप्स रूट नोड के साथ मिला दिया जाता है।

फ़ंक्शन सम्मिलित करें(x)
    नोड यू = नया नोड
    यू.एक्स = एक्स
    जड़ = मेल्ड(यू, जड़)
    रूट.पैरेंट = शून्य
    वृद्धि नोड गिनती

निकालें

इन्सर्ट ऑपरेशन के समान ही आसान, रिमूव() हीप से रूट नोड को हटाने के लिए मेल्ड ऑपरेशन का उपयोग करता है। यह बस रूट नोड के दो बच्चों को मिलाकर और लौटाए गए नोड को नया रूट बनाकर किया जाता है।

फ़ंक्शन निकालें()
    रूट = मेल्ड (रूट.बाएं, रूट.दाएं)
    यदि रूट शून्य नहीं है => root.parent = शून्य
    नोड संख्या में कमी

FindMin

संभवतः रैंडमाइज्ड मेल्डेबल हीप के लिए सबसे आसान ऑपरेशन, फाइंडमिन () केवल हीप के रूट नोड में वर्तमान में संग्रहीत तत्व को लौटाता है।

अतिरिक्त परिचालन

कुछ अतिरिक्त संचालन जिन्हें मेल्डेबल हीप के लिए कार्यान्वित किया जा सकता है जिनमें O(logn) सबसे खराब स्थिति वाली दक्षता भी है:

• रिमूव(यू) - नोड यू और उसकी कुंजी को ढेर से हटा दें।
• अवशोषक (क्यू) - प्रक्रिया में क्यू को खाली करते हुए, इस ढेर में पिघलने योग्य ढेर क्यू के सभी तत्वों को जोड़ें।
• DecreaseKey(u, y) - नोड u में कुंजी को घटाकर y कर देता है (पूर्व शर्त: y <= u.x)।

दक्षता विश्लेषण

चूंकि सभी गैर-स्थिर-समय संचालन को मेल्ड ऑपरेशन के संदर्भ में परिभाषित किया गया है, इन परिचालनों की दक्षता दो यादृच्छिक ढेरों को मिलाने की जटिलता के विश्लेषण के माध्यम से निर्धारित की जा सकती है।

इस विश्लेषण का परिणाम यह है कि एन-नोड यादृच्छिक ढेर पर किसी भी मेल्डेबल प्राथमिकता कतार संचालन का अपेक्षित समय ओ (लॉगएन) है।

Operation	Worst-Case Time Efficiency
Meld(Q1, Q2)	O(logn)
Insert(x)	O(logn)
Remove()	O(logn)
FindMin()	O(1)
Remove(x)	O(logn)
Absorb(Q)	O(logn)

इतिहास

ऐसा प्रतीत होता है कि पिघलने योग्य ढेर पहली बार 1998 में गैम्बिन और मालिनोवस्की द्वारा प्रस्तावित किया गया था।

वेरिएंट

जबकि रैंडमाइज्ड मेल्डेबल हीप, मेल्डेबल हीप कार्यान्वयन का सबसे सरल रूप है, अन्य मौजूद हैं। ये:

• वामपंथी ढेर
• द्विपद ढेर
• फाइबोनैचि ढेर
• युग्मन ढेर
• तिरछा ढेर