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

From Vigyanwiki
(minor changes)
Line 1: Line 1:
कंप्यूटर विज्ञान में, एक यादृच्छिक मेल्डेबल हीप (मेल्डेबल हीप ([[डेटा संरचना]]) या रैंडमाइज्ड मेल्डेबल [[प्राथमिकता कतार]]) एक प्राथमिकता कतार आधारित डेटा संरचना है जिसमें अंतर्निहित संरचना भी एक हीप-ऑर्डर [[ द्विआधारी वृक्ष ]] है। हालाँकि, अंतर्निहित बाइनरी ट्री के आकार पर कोई प्रतिबंध नहीं है।
कंप्यूटर विज्ञान में, एक रैन्डमाइज्ड मेल्डेबल हीप (भी मेल्डेबल हीप या रैन्डमाइज्ड मेल्डेबल [[प्राथमिकता कतार]] के रूप में जाना जाता है) एक प्राथमिकता कतार आधारित [[डेटा संरचना]] है, जिसमें अंतर्निहित संरचना भी एक हीप-आदेशित [[ द्विआधारी वृक्ष |बाइनरी वृक्ष]] है। हालांकि, अंतर्निहित बाइनरी वृक्ष के आकार पर कोई प्रतिबंध नहीं होता।
 
समान डेटा संरचनाओं की तुलना में इस दृष्टिकोण के कई फायदे हैं। यह अधिक सरलता प्रदान करता है: यादृच्छिक मेल्डेबल ढेर के लिए सभी ऑपरेशन लागू करना आसान है और उनकी जटिलता सीमा में निरंतर कारक छोटे हैं। संतुलन स्थितियों को संरक्षित करने की भी कोई आवश्यकता नहीं है और नोड्स के भीतर कोई उपग्रह जानकारी आवश्यक नहीं है। अंत में, इस संरचना में सबसे खराब स्थिति में भी अच्छी समय दक्षता है। प्रत्येक व्यक्तिगत ऑपरेशन का निष्पादन समय उच्च संभावना के साथ अधिकतम लघुगणकीय होता है।<ref name="Gambin">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.</ref>
 


इस दृष्टिकोण से, इस तरीके के कई लाभ समान डेटा संरचनाओं की तुलना में होते हैं। यह अधिक सरलता प्रदान करता है: रैन्डमाइज्ड मेल्डेबल हीप के लिए सभी आवृत्तियां आसानी से लागू की जा सकती हैं और उनकी जटिलता सीमाओं में स्थिरांक कारक छोटे होते हैं। साथ ही, संतुलन शर्तें संरक्षित करने की आवश्यकता नहीं होती है और नोडों के भीतर कोई उपग्रह जानकारी की आवश्यकता नहीं होती। अंत में, इस संरचना में अच्छा कालांतरिक समय प्रभावशीलता होती है। प्रत्येक व्यक्तिगत आवृत्ति का क्रियान्वयन समय अधिकतम उच्च संभावना के साथ लघुगणकीय होता है।<ref name="Gambin">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.</ref>
==संचालन==
==संचालन==
रैंडमाइज्ड मेल्डेबल हीप कई सामान्य ऑपरेशनों का समर्थन करता है। ये सम्मिलन, विलोपन और एक खोज ऑपरेशन, फाइंडमिन हैं। सम्मिलन और विलोपन संचालन को मेल्डेबल हीप, मेल्ड (क्यू1, क्यू2) के लिए विशिष्ट एक अतिरिक्त ऑपरेशन के संदर्भ में कार्यान्वित किया जाता है।
रैन्डमाइज्ड मेल्डेबल हीप कई सामान्य आवृत्तियों का समर्थन करता है। इनमें सम्मिलित हैं सम्मिलन, हटाना, और खोजने की आवृत्ति। सम्मिलित और हटाने के कार्य अलग-अलग हीप के साथ एक अतिरिक्त आवृत्ति, यानी मेल्ड(Q1, Q2), के आधार पर लागू किए जाते हैं।


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


  फ़ंक्शन मेल्ड (नोड ''Q''1, नोड ''Q''2)
इस मेल्ड ऑपरेशन की एक अच्छी सुविधा यह है कि इसे पुनरावर्ती रूप से परिभाषित किया जा सकता है। यदि दोनों में से कोई भी ढेर शून्य है, तो मर्ज एक खाली सेट के साथ हो रहा है और विधि केवल गैर-खाली ढेर का रूट नोड लौटाती है। यदि Q1 और Q2 दोनों शून्य नहीं हैं, तो जाँचें कि क्या Q1 > Q2 है। यदि ऐसा है, तो दोनों की अदला-बदली करें। इसलिए यह सुनिश्चित किया गया है कि Q1 <Q2 और मर्ज किए गए ढेर के रूट नोड में Q1 होगा। फिर हम Q2 को Q1.left या Q1.right के साथ पुनरावर्ती रूप से मर्ज करते हैं। यह वह चरण है जहां यादृच्छिकरण आता है क्योंकि किस पक्ष के साथ विलय करना है इसका निर्णय एक सिक्का उछालकर निर्धारित किया जाता है।
     यदि ''Q''1 शून्य है => ''Q''2 लौटाएँ
  '''function''' Meld('''Node''' ''Q''1, '''Node''' ''Q''2)
     यदि ''Q''2 शून्य है => ''Q''1 लौटाएँ
     '''if''' ''Q''1 is nil => '''return''' ''Q''2
     यदि ''Q1'' > ''Q''2 => ''Q''1 और ''Q''2 को स्वैप करें
     '''if''' ''Q''2 is nil => '''return''' ''Q''1
     यदि coin_toss 0 है => ''Q''1.''left'' = Meld(''Q''1.''left'', ''Q''2)
     '''if''' ''Q1'' > ''Q''2 => swap ''Q''1 and ''Q''2
     अन्यथा ''क्यू''1.''दाएं'' = मेल्ड(''क्यू''1.''दाएं'', ''क्यू''2)
     '''if''' coin_toss is 0 => ''Q''1.''left'' = Meld(''Q''1.''left'', ''Q''2)
     वापसी ''Q''1
     '''else''' ''Q''1.''right'' = Meld(''Q''1.''right'', ''Q''2)
     '''return ''Q''1'''
 


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


  फ़ंक्शन सम्मिलित करें(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)
     यदि रूट शून्य नहीं है => root.parent = शून्य
     '''if''' root is not nil => root.parent = nil
     नोड संख्या में कमी
     decrement node count


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


===अतिरिक्त परिचालन===
===अतिरिक्त परिचालन===
कुछ अतिरिक्त संचालन जिन्हें मेल्डेबल हीप के लिए कार्यान्वित किया जा सकता है जिनमें O(logn) सबसे खराब स्थिति वाली दक्षता भी है:
कुछ अतिरिक्त कार्य भी हैं जो रैन्डमाइज्ड मेल्डेबल हीप के लिए लागू किए जा सकते हैं और उनकी क्रियाकलाप की खराब स्थिति में O(logn) कालांतरिक प्रभावशीलता होती है:
* रिमूव(यू) - नोड यू और उसकी कुंजी को ढेर से हटा दें।
* Remove(u) - नोड u और उसकी कुंजी (key) को हीप से हटाएं।
* अवशोषक (क्यू) - प्रक्रिया में क्यू को खाली करते हुए, इस ढेर में पिघलने योग्य ढेर क्यू के सभी तत्वों को जोड़ें।
*Absorb(Q) - मेल्डेबल हीप Q के सभी तत्वों को इस हीप में जोड़ें, जिससे प्रक्रिया में Q खाली हो जाता है।
* DecreaseKey(u, y) - नोड u में कुंजी को घटाकर y कर देता है (पूर्व शर्त: y <= u.x)।
*DecreaseKey(u, y) - नोड u में कुंजी (key) को y तक कम करें (पूर्व-शर्त: y ≤ u.x)।


==दक्षता विश्लेषण==
==दक्षता विश्लेषण==
चूंकि सभी गैर-स्थिर-समय संचालन को मेल्ड ऑपरेशन के संदर्भ में परिभाषित किया गया है, इन परिचालनों की दक्षता दो यादृच्छिक ढेरों को मिलाने की जटिलता के विश्लेषण के माध्यम से निर्धारित की जा सकती है।
सभी गैर-निरंतर समय की क्रियाएं Meld कार्य के आधार पर परिभाषित होती हैं, इन कार्यों की प्रभावशीलता दो रैन्डमाइज्ड हीप्स को मिलाने की जटिलता के विश्लेषण के माध्यम से निर्धारित की जा सकती है।
 
इस विश्लेषण का परिणाम यह है कि एन-नोड यादृच्छिक ढेर पर किसी भी मेल्डेबल प्राथमिकता कतार संचालन का अपेक्षित समय ओ (लॉगएन) है।<ref name="Gambin" /><ref name="Morin">[[Pat Morin|P. Morin]], [http://opendatastructures.org/ods-java.pdf] Open Data Structures, p. 191-</ref>


इस विश्लेषण के परिणामस्वरूप, किसी भी n-नोड रैन्डमाइज्ड हीप पर किसी भी मेल्डेबल प्राथमिकता कतार के किसी भी कार्य का अपेक्षित समय O(logn) होता है।<ref name="Gambin" /><ref name="Morin">[[Pat Morin|P. Morin]], [http://opendatastructures.org/ods-java.pdf] Open Data Structures, p. 191-</ref>
{| class="wikitable"
{| class="wikitable"
|-
|-
! Operation !! Worst-Case Time Efficiency
! संक्रिया !! वॉर्स-केस टाइम एफिशिएंसी
|-
|-
| Meld(Q1, Q2) || ''O''(log''n'')
| Meld(Q1, Q2) || ''O''(log''n'')
Line 68: Line 65:
| Absorb(Q) || ''O''(log''n'')
| Absorb(Q) || ''O''(log''n'')
|}
|}
==इतिहास==
==इतिहास==
ऐसा प्रतीत होता है कि पिघलने योग्य ढेर पहली बार 1998 में गैम्बिन और मालिनोवस्की द्वारा प्रस्तावित किया गया था।<ref name="Gambin" />
ऐसा प्रतीत होता है कि पिघलने योग्य ढेर को पहली बार 1998 में गैम्बिन और मालिनोवस्की द्वारा प्रस्तावित किया गया था।<ref name="Gambin" />
 
 
==वेरिएंट==
==वेरिएंट==
जबकि रैंडमाइज्ड मेल्डेबल हीप, मेल्डेबल हीप कार्यान्वयन का सबसे सरल रूप है, अन्य मौजूद हैं। ये:
जबकि यादृच्छिक मेल्डेबल हीप मेल्डेबल हीप कार्यान्वयन का सबसे सरल रूप है, अन्य मौजूद हैं। ये:
*[[वामपंथी ढेर]]
*[[वामपंथी ढेर|लेफ्टिस्ट हीप]]  
*[[द्विपद ढेर]]
*[[द्विपद ढेर|बाईनोमिअल हीप]]
*[[फाइबोनैचि ढेर]]
*[[फाइबोनैचि ढेर|फिबोनाची हीप]]
*[[युग्मन ढेर]]
*[[युग्मन ढेर|पैरिंग हीप]]
*[[तिरछा ढेर]]
*[[तिरछा ढेर|स्क्यू हीप]]


==संदर्भ==
==संदर्भ==

Revision as of 09:55, 22 July 2023

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

इस दृष्टिकोण से, इस तरीके के कई लाभ समान डेटा संरचनाओं की तुलना में होते हैं। यह अधिक सरलता प्रदान करता है: रैन्डमाइज्ड मेल्डेबल हीप के लिए सभी आवृत्तियां आसानी से लागू की जा सकती हैं और उनकी जटिलता सीमाओं में स्थिरांक कारक छोटे होते हैं। साथ ही, संतुलन शर्तें संरक्षित करने की आवश्यकता नहीं होती है और नोडों के भीतर कोई उपग्रह जानकारी की आवश्यकता नहीं होती। अंत में, इस संरचना में अच्छा कालांतरिक समय प्रभावशीलता होती है। प्रत्येक व्यक्तिगत आवृत्ति का क्रियान्वयन समय अधिकतम उच्च संभावना के साथ लघुगणकीय होता है।[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. ↑ 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.
  2. ↑ P. Morin, [1] Open Data Structures, p. 191-
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=यादृच्छिक_मेल्डेबल_हीप&oldid=228866’