यादृच्छिक मेल्डेबल हीप
कंप्यूटर विज्ञान में, एक रैन्डमाइज्ड मेल्डेबल हीप (भी मेल्डेबल हीप या रैन्डमाइज्ड मेल्डेबल प्राथमिकता कतार के रूप में जाना जाता है) एक प्राथमिकता कतार आधारित डेटा संरचना है, जिसमें अंतर्निहित संरचना भी एक हीप-आदेशित बाइनरी वृक्ष है। हालांकि, अंतर्निहित बाइनरी वृक्ष के आकार पर कोई प्रतिबंध नहीं होता।
इस दृष्टिकोण से, इस तरीके के कई लाभ समान डेटा संरचनाओं की तुलना में होते हैं। यह अधिक सरलता प्रदान करता है: रैन्डमाइज्ड मेल्डेबल हीप के लिए सभी आवृत्तियां आसानी से लागू की जा सकती हैं और उनकी जटिलता सीमाओं में स्थिरांक कारक छोटे होते हैं। साथ ही, संतुलन शर्तें संरक्षित करने की आवश्यकता नहीं होती है और नोडों के भीतर कोई उपग्रह जानकारी की आवश्यकता नहीं होती। अंत में, इस संरचना में अच्छा कालांतरिक समय प्रभावशीलता होती है। प्रत्येक व्यक्तिगत आवृत्ति का क्रियान्वयन समय अधिकतम उच्च संभावना के साथ लघुगणकीय होता है।[1]
संचालन
रैन्डमाइज्ड मेल्डेबल हीप कई सामान्य आवृत्तियों का समर्थन करता है। इनमें सम्मिलित हैं सम्मिलन, हटाना, और खोजने की आवृत्ति। सम्मिलित और हटाने के कार्य अलग-अलग हीप के साथ एक अतिरिक्त आवृत्ति, यानी मेल्ड(Q1, Q2), के आधार पर लागू किए जाते हैं।
मेल्ड
मेल्ड (जिसे मर्ज भी कहा जाता है) ऑपरेशन का मूल लक्ष्य दो हीप्स (प्रत्येक हीप्स रूट नोड्स लेकर), Q1 और Q2 लेना है, और उन्हें मर्ज करना है, परिणामस्वरूप एक ही हीप नोड वापस आता है। यह हीप नोड एक हीप का मूल नोड है जिसमें Q1 और Q2 पर निहित दो उपवृक्षों के सभी तत्व शामिल हैं।
इस मेल्ड ऑपरेशन की एक अच्छी सुविधा यह है कि इसे पुनरावर्ती रूप से परिभाषित किया जा सकता है। यदि दोनों में से कोई भी ढेर शून्य है, तो मर्ज एक खाली सेट के साथ हो रहा है और विधि केवल गैर-खाली ढेर का रूट नोड लौटाती है। यदि Q1 और Q2 दोनों शून्य नहीं हैं, तो जाँचें कि क्या Q1 > Q2 है। यदि ऐसा है, तो दोनों की अदला-बदली करें। इसलिए यह सुनिश्चित किया गया है कि Q1 <Q2 और मर्ज किए गए ढेर के रूट नोड में Q1 होगा। फिर हम Q2 को Q1.left या Q1.right के साथ पुनरावर्ती रूप से मर्ज करते हैं। यह वह चरण है जहां यादृच्छिकरण आता है क्योंकि किस पक्ष के साथ विलय करना है इसका निर्णय एक सिक्का उछालकर निर्धारित किया जाता है।
function Meld(Node Q1, Node Q2)
if Q1 is nil => return Q2
if Q2 is nil => return Q1
if Q1 > Q2 => swap Q1 and Q2
if coin_toss is 0 => Q1.left = Meld(Q1.left, Q2)
else Q1.right = Meld(Q1.right, Q2)
return Q1
सम्मिलित करें
सम्मिलित क्रिया पूर्ण होने के बाद, रैन्डमाइज्ड मेल्डेबल हीप में सम्मिलित करना आसान हो जाता है। पहले, एक नया नोड, u, बनाया जाता है, जिसमें मान x होता है। फिर, यह नया नोड सिंपली हीप के जड़ नोड के साथ सम्मिलित कर दिया जाता है।
function Insert(x)
Node u = new Node
u.x = x
root = Meld(u, root)
root.parent = nil
increment node count
निकालें
इसी तरह से, हटाने कार्य भी सम्मिलित क्रिया का उपयोग करता है ताकि हीप से जड़ नोड को नष्ट किया जा सके। इसके लिए बस हीप के जड़ नोड के दो बच्चों को सम्मिलित कर दिया जाता है और वापस मिले नोड को नया जड़ नोड बना दिया जाता है।
function Remove()
root = Meld(root.left, root.right)
if root is not nil => root.parent = nil
decrement node count
FindMin
शायद रैन्डमाइज्ड मेल्डेबल हीप के लिए सबसे सरल कार्य, FindMin() केवल हीप के जड़ नोड में संग्रहीत तत्व को वापस लौटा देता है।
अतिरिक्त परिचालन
कुछ अतिरिक्त कार्य भी हैं जो रैन्डमाइज्ड मेल्डेबल हीप के लिए लागू किए जा सकते हैं और उनकी क्रियाकलाप की खराब स्थिति में O(logn) कालांतरिक प्रभावशीलता होती है:
- Remove(u) - नोड u और उसकी कुंजी (key) को हीप से हटाएं।
- Absorb(Q) - मेल्डेबल हीप Q के सभी तत्वों को इस हीप में जोड़ें, जिससे प्रक्रिया में Q खाली हो जाता है।
- DecreaseKey(u, y) - नोड u में कुंजी (key) को y तक कम करें (पूर्व-शर्त: y ≤ u.x)।
दक्षता विश्लेषण
सभी गैर-निरंतर समय की क्रियाएं Meld कार्य के आधार पर परिभाषित होती हैं, इन कार्यों की प्रभावशीलता दो रैन्डमाइज्ड हीप्स को मिलाने की जटिलता के विश्लेषण के माध्यम से निर्धारित की जा सकती है।
इस विश्लेषण के परिणामस्वरूप, किसी भी n-नोड रैन्डमाइज्ड हीप पर किसी भी मेल्डेबल प्राथमिकता कतार के किसी भी कार्य का अपेक्षित समय O(logn) होता है।[1][2]
| संक्रिया | वॉर्स-केस टाइम एफिशिएंसी |
|---|---|
| Meld(Q1, Q2) | O(logn) |
| Insert(x) | O(logn) |
| Remove() | O(logn) |
| FindMin() | O(1) |
| Remove(x) | O(logn) |
| Absorb(Q) | O(logn) |
इतिहास
ऐसा प्रतीत होता है कि पिघलने योग्य ढेर को पहली बार 1998 में गैम्बिन और मालिनोवस्की द्वारा प्रस्तावित किया गया था।[1]
वेरिएंट
जबकि यादृच्छिक मेल्डेबल हीप मेल्डेबल हीप कार्यान्वयन का सबसे सरल रूप है, अन्य मौजूद हैं। ये:
संदर्भ
- ↑ 1.0 1.1 1.2 A. Gambin and A. Malinowski. 1998. Randomized Meldable Priority Queues. In Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics: Theory and Practice of Informatics (SOFSEM '98), Branislav Rovan (Ed.). Springer-Verlag, London, UK, UK, 344-349.
- ↑ P. Morin, [1] Open Data Structures, p. 191-
