यादृच्छिक मेल्डेबल हीप
कंप्यूटर विज्ञान में, रैन्डमाइज्ड मेल्डेबल हीप (भी मेल्डेबल हीप या रैन्डमाइज्ड मेल्डेबल प्राथमिकता कतार (प्रायोरिटी क्यू) के रूप में जाना जाता है) प्राथमिकता कतार आधारित डाटा स्ट्रक्चर है, जिसमें अंतर्निहित संरचना भी एक हीप-ऑर्डर्ड बाइनरी ट्री है। हालांकि, अंतर्निहित बाइनरी ट्री के आकार पर कोई प्रतिबंध नहीं होता।
इस दृष्टिकोण से, इस तरीके के कई लाभ समान डाटा स्ट्रक्चर्स की तुलना में होते हैं। यह अधिक सरलता प्रदान करता है: रैन्डमाइज्ड मेल्डेबल हीप के लिए सभी आवृत्तियां सरलता से लागू की जा सकती हैं और उनकी जटिलता सीमाओं में स्थिरांक कारक छोटे होते हैं। साथ ही, संतुलन शर्तें संरक्षित करने की आवश्यकता नहीं होती है और नोडों के भीतर कोई उपग्रह जानकारी की आवश्यकता नहीं होती। अंत में, इस संरचना में अच्छा कालांतरिक समय प्रभावशीलता होती है। प्रत्येक व्यक्तिगत आवृत्ति का क्रियान्वयन समय अधिकतम उच्च संभावना के साथ लघुगणकीय होता है।[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
फाइंडमिन
रैंडमाइज्ड मेल्डेबल हीप के लिए संभवत: सबसे आसान ऑपरेशन, फाइंडमिन() केवल हीप के रूट नोड में वर्तमान में संग्रहीत तत्व को रिटर्न करता है।
अतिरिक्त संक्रिया
कुछ अतिरिक्त संक्रिया भी हैं जो रैन्डमाइज्ड मेल्डेबल हीप के लिए लागू किए जा सकते हैं और उनकी क्रियाकलाप की खराब स्थिति में O(logn) कालांतरिक प्रभावशीलता होती है:
- Remove(u) - नोड u और उसकी कुंजी को हीप से हटाएं।
- Absorb(Q) - मेल्डेबल हीप Q के सभी तत्वों को इस हीप में जोड़ें, जिससे प्रक्रिया में Q रिक्त हो जाता है।
- DecreaseKey(u, y) - नोड u में कुंजी (key) को y तक कम करें (पूर्व-शर्त: y <= u.x)।
दक्षता विश्लेषण
चूंकि सभी गैर-स्थिर-समय संचालन को मेल्ड ऑपरेशन के संदर्भ में परिभाषित किया गया है, इन ऑपरेशनों की दक्षता दो रैन्डमाइज्ड हीप्स को मिलाने की जटिलता के विश्लेषण के माध्यम से निर्धारित की जा सकती है।
इस विश्लेषण के परिणामस्वरूप, किसी भी 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-
