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

From Vigyanwiki
(minor changes)
(Work done)
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), के आधार पर लागू किए जाते हैं।
रैंडमाइज्ड मेल्डेबल हीप कई सामान्य ऑपरेशनों का समर्थन करता है। इनमें इंसर्शन, डिलीशन, और सर्चिंग ऑपरेशन, फाइंडमिन सम्मिलित हैं। इंसर्शन और डिलीशन की संक्रिया अलग-अलग हीप के साथ एक अतिरिक्त संक्रिया, अर्थात मेल्ड(Q1, Q2), के आधार पर लागू किए जाते हैं।


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


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


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


  '''function''' Insert(x)
  '''function''' Insert(x)
Line 28: Line 28:
     increment node count
     increment node count


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


  '''function''' Remove()
  '''function''' Remove()
Line 36: Line 36:
     decrement node count
     decrement node count


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


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


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


इस विश्लेषण के परिणामस्वरूप, किसी भी 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>
इस विश्लेषण के परिणामस्वरूप, किसी भी 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>
Line 66: Line 66:
|}
|}
==इतिहास==
==इतिहास==
ऐसा प्रतीत होता है कि पिघलने योग्य ढेर को पहली बार 1998 में गैम्बिन और मालिनोवस्की द्वारा प्रस्तावित किया गया था।<ref name="Gambin" />
गैम्बिन और मालिनोव्स्की ने 1998 में पहली बार मेल्डबल हीप की प्रस्तावना की थी।<ref name="Gambin" />
==वेरिएंट==
==वेरिएंट==
जबकि यादृच्छिक मेल्डेबल हीप मेल्डेबल हीप कार्यान्वयन का सबसे सरल रूप है, अन्य मौजूद हैं। ये:
जबकि रैन्डमाइज़्ड मेल्डबल हीप मेल्डबल हीप के सबसे सरल रूप है, अन्य भी हैं जो विद्यमान हैं। इनमें सम्मिलित हैं:
*[[वामपंथी ढेर|लेफ्टिस्ट हीप]]  
*[[वामपंथी ढेर|लेफ्टिस्ट हीप]]  
*[[द्विपद ढेर|बाईनोमिअल हीप]]
*[[द्विपद ढेर|बाईनोमिअल हीप]]

Revision as of 08:18, 24 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=228867’