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

From Vigyanwiki
(Created page with "कंप्यूटर विज्ञान में, एक यादृच्छिक मेल्डेबल हीप (मेल्डेबल हीप (डे...")
 
No edit summary
 
(5 intermediate revisions by 4 users not shown)
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>
 
==संक्रिया==
 
रैंडमाइज्ड मेल्डेबल हीप कई सामान्य ऑपरेशनों का समर्थन करता है। इनमें इंसर्शन, डिलीशन, और सर्चिंग ऑपरेशन, फाइंडमिन सम्मिलित हैं। इंसर्शन और डिलीशन की संक्रिया अलग-अलग हीप के साथ एक अतिरिक्त संक्रिया, अर्थात मेल्ड(Q1, Q2), के आधार पर लागू किए जाते हैं।
==संचालन==
रैंडमाइज्ड मेल्डेबल हीप कई सामान्य ऑपरेशनों का समर्थन करता है। ये सम्मिलन, विलोपन और एक खोज ऑपरेशन, फाइंडमिन हैं। सम्मिलन और विलोपन संचालन को मेल्डेबल हीप, मेल्ड (क्यू1, क्यू2) के लिए विशिष्ट एक अतिरिक्त ऑपरेशन के संदर्भ में कार्यान्वित किया जाता है।


===मेल्ड===
===मेल्ड===
मेल्ड (जिसे मर्ज भी कहा जाता है) ऑपरेशन का मूल लक्ष्य दो हीप्स (प्रत्येक हीप्स रूट नोड्स लेकर), 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===
===फाइंडमिन===
संभवतः रैंडमाइज्ड मेल्डेबल हीप के लिए सबसे आसान ऑपरेशन, फाइंडमिन () केवल हीप के रूट नोड में वर्तमान में संग्रहीत तत्व को लौटाता है।
रैंडमाइज्ड मेल्डेबल हीप के लिए संभवत: सबसे आसान ऑपरेशन, फाइंडमिन() केवल हीप के रूट नोड में वर्तमान में संग्रहीत तत्व को रिटर्न करता है।


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


==दक्षता विश्लेषण==
==दक्षता विश्लेषण==
चूंकि सभी गैर-स्थिर-समय संचालन को मेल्ड ऑपरेशन के संदर्भ में परिभाषित किया गया है, इन परिचालनों की दक्षता दो यादृच्छिक ढेरों को मिलाने की जटिलता के विश्लेषण के माध्यम से निर्धारित की जा सकती है।
चूंकि सभी गैर-स्थिर-समय संचालन को मेल्ड ऑपरेशन के संदर्भ में परिभाषित किया गया है, इन ऑपरेशनों की दक्षता दो रैन्डमाइज्ड हीप्स को मिलाने की जटिलता के विश्लेषण के माध्यम से निर्धारित की जा सकती है।
 
इस विश्लेषण का परिणाम यह है कि एन-नोड यादृच्छिक ढेर पर किसी भी मेल्डेबल प्राथमिकता कतार संचालन का अपेक्षित समय ओ (लॉगएन) है।<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" />
 
 
==वेरिएंट==
==वेरिएंट==
जबकि रैंडमाइज्ड मेल्डेबल हीप, मेल्डेबल हीप कार्यान्वयन का सबसे सरल रूप है, अन्य मौजूद हैं। ये:
जबकि रैन्डमाइज़्ड मेल्डबल हीप मेल्डबल हीप के सबसे सरल रूप है, अन्य भी हैं जो विद्यमान हैं। इनमें सम्मिलित हैं:
*[[वामपंथी ढेर]]
*[[वामपंथी ढेर|लेफ्टिस्ट हीप]]  
*[[द्विपद ढेर]]
*[[द्विपद ढेर|बाईनोमिअल हीप]]
*[[फाइबोनैचि ढेर]]
*[[फाइबोनैचि ढेर|फिबोनाची हीप]]
*[[युग्मन ढेर]]
*[[युग्मन ढेर|पैरिंग हीप]]
*[[तिरछा ढेर]]
*[[तिरछा ढेर|स्क्यू हीप]]


==संदर्भ==
==संदर्भ==
{{reflist}}
{{reflist}}


[[Category: प्राथमिकता कतारें]]
[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:प्राथमिकता कतारें]]

Latest revision as of 14:37, 28 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

फाइंडमिन

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

अतिरिक्त संक्रिया

कुछ अतिरिक्त संक्रिया भी हैं जो रैन्डमाइज्ड मेल्डेबल हीप के लिए लागू किए जा सकते हैं और उनकी क्रियाकलाप की खराब स्थिति में 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. ↑ 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=229298’