द्विपद हीप: Difference between revisions
No edit summary |
No edit summary |
||
| Line 9: | Line 9: | ||
* ऑर्डर <math>k</math> के एक बायनोमिअल ट्री में एक रूट नोड होता है जिसके चिल्ड्रन ऑर्डर <math>k-1</math>, <math>k-2</math>, ..., 2, 1, 0 (इस ऑर्डर में) के बायनोमिअल ट्रीज की रूटें होती हैं। | * ऑर्डर <math>k</math> के एक बायनोमिअल ट्री में एक रूट नोड होता है जिसके चिल्ड्रन ऑर्डर <math>k-1</math>, <math>k-2</math>, ..., 2, 1, 0 (इस ऑर्डर में) के बायनोमिअल ट्रीज की रूटें होती हैं। | ||
[[File:Binomial Trees.svg|center|thumb|500px|0 से 3 ऑर्डर के बायनोमिअल ट्री: प्रत्येक ट्री में सभी निचले ऑर्डर वाले बायनोमिअल ट्रीज के | [[File:Binomial Trees.svg|center|thumb|500px|0 से 3 ऑर्डर के बायनोमिअल ट्री: प्रत्येक ट्री में सभी निचले ऑर्डर वाले बायनोमिअल ट्रीज के सबट्रीज के साथ एक रूट नोड होता है, जिसे हाइलाइट किया गया है। उदाहरण के लिए, ऑर्डर 3 बायनोमिअल ट्री ऑर्डर 2, 1, और 0 (क्रमशः नीले, हरे और लाल के रूप में हाइलाइट किया गया) बायनोमिअल ट्री से जुड़ा है।]]ऑर्डर <math>k</math> के एक बायनोमिअल ट्री में <math>2^k</math> नोड्स हैं, और ऊंचाई <math>k</math> है। नाम साइज से प्राप्त होता है: ऑर्डर <math>k</math> के बायनोमिअल ट्री में डेप्थ <math>d</math> पर <math>\tbinom k d</math> नोड्स हैं, जो एक बायनोमिअल गुणांक है। इसकी संरचना के कारण, ऑर्डर <math>k</math> के एक बायनोमिअल ट्री का निर्माण ऑर्डर <math>k-1</math> के दो ट्रीज से किया जा सकता है, उनमें से एक को दूसरे ट्री की रूट के सर्वाधिक बाएं चाइल्ड के रूप में ''मर्ज'' जा सकता है। यह सुविधा बायनोमिअल हीप के मर्ज ऑपरेशन के लिए केंद्रीय है, जो अन्य पारंपरिक हीप्स की तुलना में इसका प्रमुख लाभ है।<ref name="clrs" /><ref name="brown">{{cite journal|last=Brown|first=Mark R.|doi=10.1137/0207026|issue=3|journal=SIAM Journal on Computing|mr=483830|pages=298–319|title=द्विपद कतार एल्गोरिदम का कार्यान्वयन और विश्लेषण|volume=7|year=1978}}</ref> | ||
== बायनोमिअल हीप की संरचना == | == बायनोमिअल हीप की संरचना == | ||
एक बायनोमिअल हीप को बायनोमिअल ट्रीज के एक सेट के रूप में लागू किया जाता है जो बायनोमिअल हीप गुणों को संतुष्ट करता है:<ref name="clrs" /> | एक बायनोमिअल हीप को बायनोमिअल ट्रीज के एक सेट के रूप में लागू किया जाता है जो बायनोमिअल हीप गुणों को संतुष्ट करता है:<ref name="clrs" /> | ||
* हीप में प्रत्येक बायनोमिअल ट्री [[न्यूनतम-ढेर संपत्ति|''मिनिमम-हीप गुणधर्म'']] का पालन करता है: एक नोड की | * हीप में प्रत्येक बायनोमिअल ट्री [[न्यूनतम-ढेर संपत्ति|''मिनिमम-हीप गुणधर्म'']] का पालन करता है: एक नोड की कुंजी (की) उसके मूल की कुंजी से बड़ी या उसके बराबर होती है। | ||
* प्रत्येक ऑर्डर के लिए, शून्य ऑर्डर सहित, अधिकतम एक बायनोमिअल ट्री हो सकता है। | * प्रत्येक ऑर्डर के लिए, शून्य ऑर्डर सहित, अधिकतम एक बायनोमिअल ट्री हो सकता है। | ||
प्रथम गुणधर्म यह सुनिश्चित करती है कि प्रत्येक बायनोमिअल ट्री की रूट में ट्री की सबसे छोटी | प्रथम गुणधर्म यह सुनिश्चित करती है कि प्रत्येक बायनोमिअल ट्री की रूट में ट्री की सबसे छोटी कुंजी सम्मिलित है। इसका अर्थ यह है कि पूरे हीप में सबसे छोटी कुंजी रूट्स में से एक है।<ref name="clrs" /> | ||
किसी बायनोमिअल हीप को बायनोमिअल ट्रीज के एक सेट के रूप में कार्यान्वित किया जाता है जो बायनोमिअल हीप गुणों को संतुष्ट करते हैं:* हीप में प्रत्येक बायनोमिअल ट्री का पालन करता है: एक नोड की | किसी बायनोमिअल हीप को बायनोमिअल ट्रीज के एक सेट के रूप में कार्यान्वित किया जाता है जो बायनोमिअल हीप गुणों को संतुष्ट करते हैं:* हीप में प्रत्येक बायनोमिअल ट्री का पालन करता है: एक नोड की कुंजी उसके मूल की कुंजी से बड़ी या उसके बराबर होती है। | ||
द्वितीय गुणधर्म का तात्पर्य है कि <math>n</math> नोड्स वाले एक बायनोमिअल हीप में अधिकतम <math>1+\log_2 n</math> बायनोमिअल ट्री होते हैं, जहां <math>\log_2</math> [[द्विआधारी लघुगणक|बायनोमिअल लघुगणक]] है। इन ट्रीज की संख्या और ऑर्डर विशिष्ट रूप से नोड्स <math>n</math> की संख्या से निर्धारित होते हैं: संख्या <math>n</math> के [[द्विआधारी अंक प्रणाली|बाइनरी]] प्रतिनिधित्व में प्रत्येक गैर-शून्य बिट के लिए एक बायनोमिअल ट्री होता है। उदाहरण के लिए, दशमलव संख्या 13 बाइनरी में 1101 है, <math>2^3 + 2^2 + 2^0</math>, और इस प्रकार 13 नोड्स वाले एक बायनोमिअल हीप में ऑर्डर 3, 2, और 0 के तीन बायनोमिअल ट्री सम्मिलित होंगे (नीचे चित्र देखें)।<ref name="clrs" /><ref name="brown" /> | द्वितीय गुणधर्म का तात्पर्य है कि <math>n</math> नोड्स वाले एक बायनोमिअल हीप में अधिकतम <math>1+\log_2 n</math> बायनोमिअल ट्री होते हैं, जहां <math>\log_2</math> [[द्विआधारी लघुगणक|बायनोमिअल लघुगणक]] है। इन ट्रीज की संख्या और ऑर्डर विशिष्ट रूप से नोड्स <math>n</math> की संख्या से निर्धारित होते हैं: संख्या <math>n</math> के [[द्विआधारी अंक प्रणाली|बाइनरी]] प्रतिनिधित्व में प्रत्येक गैर-शून्य बिट के लिए एक बायनोमिअल ट्री होता है। उदाहरण के लिए, दशमलव संख्या 13 बाइनरी में 1101 है, <math>2^3 + 2^2 + 2^0</math>, और इस प्रकार 13 नोड्स वाले एक बायनोमिअल हीप में ऑर्डर 3, 2, और 0 के तीन बायनोमिअल ट्री सम्मिलित होंगे (नीचे चित्र देखें)।<ref name="clrs" /><ref name="brown" /> | ||
[[File:Binomial-heap-13.svg|alt=Example of a binomial heap|center|325px|अंगूठे ऑर्डर वाले तीन बायनोमिअल ट्री हैं]]विभिन्न | [[File:Binomial-heap-13.svg|alt=Example of a binomial heap|center|325px|अंगूठे ऑर्डर वाले तीन बायनोमिअल ट्री हैं]]विभिन्न कुंजियाँ वाली <math>n</math> वस्तुओं को एक बायनोमिअल हीप में व्यवस्थित करने के विभिन्न तरीकों की संख्या <math>n!</math> के सबसे बड़े विषम भाजक के बराबर होती है। <math>n=1,2,3,\dots</math> के लिए ये संख्याएँ हैं | ||
:1, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, ... {{OEIS|A049606}} | :1, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, ... {{OEIS|A049606}} | ||
यदि 11 वस्तुओं को समान रूप से यादृच्छिक ऑर्डर में बायनोमिअल हीप में डाला जाता है, तो इनमें से प्रत्येक व्यवस्था समान रूप से संभावित है।<ref name="brown" /> | यदि 11 वस्तुओं को समान रूप से यादृच्छिक ऑर्डर में बायनोमिअल हीप में डाला जाता है, तो इनमें से प्रत्येक व्यवस्था समान रूप से संभावित है।<ref name="brown" /> | ||
| Line 29: | Line 29: | ||
क्योंकि किसी भी ऑपरेशन के लिए बायनोमिअल ट्रीज के मूल नोड्स तक यादृच्छिक पहुंच की आवश्यकता नहीं होती है, बायनोमिअल ट्रीज की रूट्स को ट्री के बढ़ते ऑर्डर के अनुसार एक लिंक की गई सूची में संग्रहीत किया जा सकता है। चूँकि प्रत्येक नोड के लिए बच्चों की संख्या परिवर्तनशील है, इसलिए प्रत्येक नोड के लिए अपने प्रत्येक चाइल्ड के लिए अलग-अलग लिंक रखना अच्छी तरह से काम नहीं करता है, जैसा कि एक बाइनरी ट्री में आम होगा; इसके बजाय, प्रत्येक नोड से ट्री में उसके उच्चतम-ऑर्डर वाले चाइल्ड और उससे अगले छोटे ऑर्डर के उसके भाई-बहन के लिंक का उपयोग करके इस ट्री को लागू करना संभव है। इन सिबलिंग पॉइंटर्स को प्रत्येक नोड के बच्चों की लिंक की गई सूची में अगले पॉइंटर्स के रूप में व्याख्या किया जा सकता है, लेकिन रूट्स की लिंक की गई सूची से विपरीत ऑर्डर के साथ: सबसे बड़े से सबसे छोटे ऑर्डर के बजाय, इसके विपरीत। यह प्रतिनिधित्व एक ही ऑर्डर के दो ट्रीज को एक साथ जोड़ने की अनुमति देता है, जिससे निरंतर समय में अगले बड़े ऑर्डर का ट्री बनता है। | क्योंकि किसी भी ऑपरेशन के लिए बायनोमिअल ट्रीज के मूल नोड्स तक यादृच्छिक पहुंच की आवश्यकता नहीं होती है, बायनोमिअल ट्रीज की रूट्स को ट्री के बढ़ते ऑर्डर के अनुसार एक लिंक की गई सूची में संग्रहीत किया जा सकता है। चूँकि प्रत्येक नोड के लिए बच्चों की संख्या परिवर्तनशील है, इसलिए प्रत्येक नोड के लिए अपने प्रत्येक चाइल्ड के लिए अलग-अलग लिंक रखना अच्छी तरह से काम नहीं करता है, जैसा कि एक बाइनरी ट्री में आम होगा; इसके बजाय, प्रत्येक नोड से ट्री में उसके उच्चतम-ऑर्डर वाले चाइल्ड और उससे अगले छोटे ऑर्डर के उसके भाई-बहन के लिंक का उपयोग करके इस ट्री को लागू करना संभव है। इन सिबलिंग पॉइंटर्स को प्रत्येक नोड के बच्चों की लिंक की गई सूची में अगले पॉइंटर्स के रूप में व्याख्या किया जा सकता है, लेकिन रूट्स की लिंक की गई सूची से विपरीत ऑर्डर के साथ: सबसे बड़े से सबसे छोटे ऑर्डर के बजाय, इसके विपरीत। यह प्रतिनिधित्व एक ही ऑर्डर के दो ट्रीज को एक साथ जोड़ने की अनुमति देता है, जिससे निरंतर समय में अगले बड़े ऑर्डर का ट्री बनता है। | ||
=== मर्ज === | === मर्ज === | ||
[[File:Binomial heap merge1.svg|thumb|200px|एक ही ऑर्डर के दो बायनोमिअल ट्रीज को मर्ज करने के लिए, पहले रूट | [[File:Binomial heap merge1.svg|thumb|200px|एक ही ऑर्डर के दो बायनोमिअल ट्रीज को मर्ज करने के लिए, पहले रूट कुंजी की तुलना करें। 7>3 के बाद से, बाईं ओर का काला ट्री (रूट नोड 7 के साथ) दाईं ओर के भूरे ट्री से (रूट नोड 3 के साथ) एक सबट्री के रूप में जुड़ा हुआ है। परिणाम ऑर्डर 3 का एक ट्री है।]]दो हीप्स को '''मर्जिंग''' का ऑपरेशन को अधिकांश अन्य ऑपरेशनों में एक सबरूटीन के रूप में उपयोग किया जाता है। इस प्रक्रिया के भीतर एक मूल सबरूटीन, एक ही ऑर्डर के बाइनोमियल ट्री के जोड़ा बनाने के लिए उपयोग किया जाता है। इसे दो ट्री के रूट्स पर मौजूद कुंजियाँ की तुलना करके किया जा सकता है (दोनों ट्री में सबसे छोटी कुंजियाँ)। बड़े कुंजी वाले रूट नोड को छोटे कुंजी वाले रूट नोड का एक चाइल्ड बनाया जाता है, जिससे उसका ऑर्डर एक के साथ बढ़ जाता है:<ref name="clrs" /><ref name="brown" /> | ||
'''function''' mergeTree(p, q) | '''function''' mergeTree(p, q) | ||
'''if''' p.root. | '''if''' p.root.कुंजी <= q.root.कुंजी | ||
'''return''' p.addSubTree(q) | '''return''' p.addSubTree(q) | ||
'''else''' | '''else''' | ||
| Line 70: | Line 70: | ||
=== डिलीट मिनिमम === | === डिलीट मिनिमम === | ||
हीप से '''मिनिमम एलिमेंट को डिलीट''' करने के लिए, सबसे पहले इस एलिमेंट को खोजें, इसे इसके बाइनोमियल ट्री के रूट से हटा दें, और इसके बच्चों के | हीप से '''मिनिमम एलिमेंट को डिलीट''' करने के लिए, सबसे पहले इस एलिमेंट को खोजें, इसे इसके बाइनोमियल ट्री के रूट से हटा दें, और इसके बच्चों के सबट्रीज की एक सूची प्राप्त करें (जो प्रत्येक अलग-अलग ऑर्डर के बाइनोमियल ट्री होते हैं)। इन सबट्रीज की सूची को छोटे से बड़े ऑर्डर तक पुनर्व्यवस्थित करके एक अलग बाइनोमियल हीप में परिवर्तित करें। फिर इस हीप को मूल हीप के साथ मर्ज करें। क्योंकि प्रत्येक रूट में अधिकतम <math>\log_2 n</math> चाइल्ड होते हैं, इस नए हीप को बनाने में समय <math>O(\log n)</math> लगता है। हीप को मर्ज करने में समय <math>O(\log n)</math> लगता है, इसलिए पूरा मिनिमम डिलीट करने ऑपरेशन का समय <math>O(\log n)</math> लगता है।<ref name="clrs" /> | ||
'''function''' deleteMin(heap) | '''function''' deleteMin(heap) | ||
min = heap.trees().first() | min = heap.trees().first() | ||
| Line 80: | Line 80: | ||
merge(heap, tmp) | merge(heap, tmp) | ||
=== डिक्रीज | === डिक्रीज कुंजी === | ||
एक एलिमेंट की | एक एलिमेंट की कुंजी को कम करने के बाद, यह अपने पैरेंट की कुंजी से छोटा हो सकता है, जिससे मिनिमम-हीप गुणवत्ता को उल्लंघन किया जाता है। यदि ऐसा है, तो एलिमेंट को अपने पैरेंट के साथ विनिमय करें, और शायद इसके साथ ही उसके ग्रैंडपेरेंट और आगे भी, जब तक मिनिमम-हीप गुणवत्ता का उल्लंघन नहीं होता है। प्रत्येक बाइनोमियल ट्री की ऊंचाई अधिकतम <math>\log_2 n</math> होती है, इसलिए इसके लिए <math>O(\log n)</math> समय लगता है।<ref name="clrs" /> हालांकि, यह ऑपरेशन यह भी आवश्यक करता है कि ट्री का प्रतिनिधि उसके पैरेंट से पॉइंटर्स को इन्सर्ट, जिससे अन्य ऑपरेशनों के अंगीकरण को कुछ प्रकार से जटिल किया जाता है।<ref name="brown" /> | ||
=== डिलीट === | === डिलीट === | ||
हीप से एक एलिमेंट को '''डिलीट''' करने के लिए, इसकी | हीप से एक एलिमेंट को '''डिलीट''' करने के लिए, इसकी कुंजी को नकारात्मक अविन्फिनिटी (या समतुल्य रूप से, हीप में किसी भी एलिमेंट से कम मान) करें और फिर हीप में मिनिमम एलिमेंट को हटा दें।<ref name="clrs" /> | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
*[[असतत घटना अनुकरण|डिस्क्रीट इवेंट सिमुलेशन]] | *[[असतत घटना अनुकरण|डिस्क्रीट इवेंट सिमुलेशन]] | ||
| Line 96: | Line 96: | ||
== बाहरी संबंध == | == बाहरी संबंध == | ||
* [http://www.cs.unc.edu/~bbb/#binomial_heaps Two C implementations of binomial heap] (a generic one and one optimized for integer | * [http://www.cs.unc.edu/~bbb/#binomial_heaps Two C implementations of binomial heap] (a generic one and one optimized for integer कुंजियाँ) | ||
* [http://hackage.haskell.org/packages/archive/TreeStructures/latest/doc/html/src/Data-Heap-Binomial.html Haskell implementation of binomial heap] | * [http://hackage.haskell.org/packages/archive/TreeStructures/latest/doc/html/src/Data-Heap-Binomial.html Haskell implementation of binomial heap] | ||
* [https://github.com/vy/binomial-heap Common Lisp implementation of binomial heap] | * [https://github.com/vy/binomial-heap Common Lisp implementation of binomial heap] | ||
Revision as of 10:07, 26 July 2023
कंप्यूटर विज्ञान में, बायनोमिअल हीप एक प्रकार डेटा स्ट्रक्चर होता है जो प्रायोरिटी क्यू के रूप में कार्य करती है लेकिन हीप के युग्मों को मर्ज करने की अनुमति भी देती है। यह मर्ज़ किए जा सकने वाले हीप एब्सट्रैक्ट डेटा टाइप (जिसे मेल्डेबल हीप भी कहा जाता है) के कार्यान्वयन के रूप में महत्वपूर्ण है, जो मर्ज ऑपरेशन का समर्थन करने वाली प्रायोरिटी क्यू है। यह एक हीप के रूप में प्रदर्शित होता है, जो बाइनरी हीप के समान होता है, लेकिन इसमें विशेष तरह का ट्री संरचना उपयोग किया जाता है जो बाइनरी हीप्स द्वारा उपयोग किए जाने वाले पूर्ण बाइनरी ट्रीज से भिन्न होता है।[1] बायनोमिअल हीप का आविष्कार 1978 में जीन वुइलेमिन ने किया था।[1][2]
बायनोमिअल हीप
एक बायनोमिअल हीप को बायनोमिअल ट्रीज के एक सेट के रूप में कार्यान्वित किया जाता है (बाइनरी हीप के साथ तुलना करें, जिसमें एकल बाइनरी ट्री का साइज होता है), जिन्हें निम्नानुसार पुनरावर्ती रूप से परिभाषित किया गया है:[1]
- ऑर्डर 0 का एक बायनोमिअल ट्री एकल नोड होता है
- ऑर्डर के एक बायनोमिअल ट्री में एक रूट नोड होता है जिसके चिल्ड्रन ऑर्डर , , ..., 2, 1, 0 (इस ऑर्डर में) के बायनोमिअल ट्रीज की रूटें होती हैं।
ऑर्डर के एक बायनोमिअल ट्री में नोड्स हैं, और ऊंचाई है। नाम साइज से प्राप्त होता है: ऑर्डर के बायनोमिअल ट्री में डेप्थ पर नोड्स हैं, जो एक बायनोमिअल गुणांक है। इसकी संरचना के कारण, ऑर्डर के एक बायनोमिअल ट्री का निर्माण ऑर्डर के दो ट्रीज से किया जा सकता है, उनमें से एक को दूसरे ट्री की रूट के सर्वाधिक बाएं चाइल्ड के रूप में मर्ज जा सकता है। यह सुविधा बायनोमिअल हीप के मर्ज ऑपरेशन के लिए केंद्रीय है, जो अन्य पारंपरिक हीप्स की तुलना में इसका प्रमुख लाभ है।[1][3]
बायनोमिअल हीप की संरचना
एक बायनोमिअल हीप को बायनोमिअल ट्रीज के एक सेट के रूप में लागू किया जाता है जो बायनोमिअल हीप गुणों को संतुष्ट करता है:[1]
- हीप में प्रत्येक बायनोमिअल ट्री मिनिमम-हीप गुणधर्म का पालन करता है: एक नोड की कुंजी (की) उसके मूल की कुंजी से बड़ी या उसके बराबर होती है।
- प्रत्येक ऑर्डर के लिए, शून्य ऑर्डर सहित, अधिकतम एक बायनोमिअल ट्री हो सकता है।
प्रथम गुणधर्म यह सुनिश्चित करती है कि प्रत्येक बायनोमिअल ट्री की रूट में ट्री की सबसे छोटी कुंजी सम्मिलित है। इसका अर्थ यह है कि पूरे हीप में सबसे छोटी कुंजी रूट्स में से एक है।[1]
किसी बायनोमिअल हीप को बायनोमिअल ट्रीज के एक सेट के रूप में कार्यान्वित किया जाता है जो बायनोमिअल हीप गुणों को संतुष्ट करते हैं:* हीप में प्रत्येक बायनोमिअल ट्री का पालन करता है: एक नोड की कुंजी उसके मूल की कुंजी से बड़ी या उसके बराबर होती है।
द्वितीय गुणधर्म का तात्पर्य है कि नोड्स वाले एक बायनोमिअल हीप में अधिकतम बायनोमिअल ट्री होते हैं, जहां बायनोमिअल लघुगणक है। इन ट्रीज की संख्या और ऑर्डर विशिष्ट रूप से नोड्स की संख्या से निर्धारित होते हैं: संख्या के बाइनरी प्रतिनिधित्व में प्रत्येक गैर-शून्य बिट के लिए एक बायनोमिअल ट्री होता है। उदाहरण के लिए, दशमलव संख्या 13 बाइनरी में 1101 है, , और इस प्रकार 13 नोड्स वाले एक बायनोमिअल हीप में ऑर्डर 3, 2, और 0 के तीन बायनोमिअल ट्री सम्मिलित होंगे (नीचे चित्र देखें)।[1][3]
विभिन्न कुंजियाँ वाली वस्तुओं को एक बायनोमिअल हीप में व्यवस्थित करने के विभिन्न तरीकों की संख्या के सबसे बड़े विषम भाजक के बराबर होती है। के लिए ये संख्याएँ हैं
यदि 11 वस्तुओं को समान रूप से यादृच्छिक ऑर्डर में बायनोमिअल हीप में डाला जाता है, तो इनमें से प्रत्येक व्यवस्था समान रूप से संभावित है।[3]
कार्यान्वयन
क्योंकि किसी भी ऑपरेशन के लिए बायनोमिअल ट्रीज के मूल नोड्स तक यादृच्छिक पहुंच की आवश्यकता नहीं होती है, बायनोमिअल ट्रीज की रूट्स को ट्री के बढ़ते ऑर्डर के अनुसार एक लिंक की गई सूची में संग्रहीत किया जा सकता है। चूँकि प्रत्येक नोड के लिए बच्चों की संख्या परिवर्तनशील है, इसलिए प्रत्येक नोड के लिए अपने प्रत्येक चाइल्ड के लिए अलग-अलग लिंक रखना अच्छी तरह से काम नहीं करता है, जैसा कि एक बाइनरी ट्री में आम होगा; इसके बजाय, प्रत्येक नोड से ट्री में उसके उच्चतम-ऑर्डर वाले चाइल्ड और उससे अगले छोटे ऑर्डर के उसके भाई-बहन के लिंक का उपयोग करके इस ट्री को लागू करना संभव है। इन सिबलिंग पॉइंटर्स को प्रत्येक नोड के बच्चों की लिंक की गई सूची में अगले पॉइंटर्स के रूप में व्याख्या किया जा सकता है, लेकिन रूट्स की लिंक की गई सूची से विपरीत ऑर्डर के साथ: सबसे बड़े से सबसे छोटे ऑर्डर के बजाय, इसके विपरीत। यह प्रतिनिधित्व एक ही ऑर्डर के दो ट्रीज को एक साथ जोड़ने की अनुमति देता है, जिससे निरंतर समय में अगले बड़े ऑर्डर का ट्री बनता है।
मर्ज
दो हीप्स को मर्जिंग का ऑपरेशन को अधिकांश अन्य ऑपरेशनों में एक सबरूटीन के रूप में उपयोग किया जाता है। इस प्रक्रिया के भीतर एक मूल सबरूटीन, एक ही ऑर्डर के बाइनोमियल ट्री के जोड़ा बनाने के लिए उपयोग किया जाता है। इसे दो ट्री के रूट्स पर मौजूद कुंजियाँ की तुलना करके किया जा सकता है (दोनों ट्री में सबसे छोटी कुंजियाँ)। बड़े कुंजी वाले रूट नोड को छोटे कुंजी वाले रूट नोड का एक चाइल्ड बनाया जाता है, जिससे उसका ऑर्डर एक के साथ बढ़ जाता है:[1][3]
function mergeTree(p, q)
if p.root.कुंजी <= q.root.कुंजी
return p.addSubTree(q)
else
return q.addSubTree(p)
दो हीप्स को अधिक सामान्यतः मर्ज करने के लिए, दोनों हीप्स की रूट्स की सूचियों को मर्ज एल्गोरिथ्म के समान तरीके से एक साथ, ट्रीज के छोटे ऑर्डर से बड़े ऑर्डर तक के ऑर्डर में ट्रेस किया जाता है। जब विलय किए जा रहे दो हीप्स में से केवल एक में ऑर्डर का ट्री होता है, तो इस ट्री को आउटपुट हीप में ले जाया जाता है। जब दोनों हीप्स में ऑर्डर का एक ट्री होता है, तो दोनों ट्रीज को ऑर्डर के एक ट्री में मिला दिया जाता है ताकि मिनिमम-हीप गुणधर्म संतुष्ट हो। बाद में इस ट्री को दो इनपुट हीप्स में से किसी एक में ऑर्डर के किसी अन्य ट्री के साथ विलय करना आवश्यक हो सकता है। एल्गोरिदम के दौरान, यह किसी भी ऑर्डर के अधिकतम तीन ट्रीज की जांच करेगा, दो हीप्स में से दो जिन्हें हम मिलाते हैं और एक दो छोटे ट्रीज से बना है।[1][3]
function merge(p, q)
while not (p.end() and q.end())
tree = mergeTree(p.currentTree(), q.currentTree())
if not heap.currentTree().empty()
tree = mergeTree(tree, heap.currentTree())
heap.addTree(tree)
heap.next(); p.next(); q.next()
क्योंकि बायनोमिअल हीप में प्रत्येक बायनोमिअल ट्री अपने साइज के बाइनरी प्रतिनिधित्व में एक बिट से मेल खाता है, दो हीप्स के विलय और दाएं से बाएं तक दो हीप्स के साइज के बाइनरी जोड़ के बीच एक समानता है। जब भी जोड़ के दौरान कोई स्थानांतरण होता है, तो यह विलय के दौरान दो बायनोमिअल ट्रीज के विलय से मेल खाता है।[1][3]
विलय के दौरान प्रत्येक बायनोमिअल ट्री के ट्रैवर्सल में केवल रूटें सम्मिलित होती हैं, इसलिए अधिकतम ऑर्डर पर लगने वाला समय बनता है और इसलिए रनिंग टाइम होता है।[1][3]
इन्सर्ट
हीप में एक नए एलिमेंट को डालने का काम सीधे एक नया हीप बनाकर किया जा सकता है जिसमें केवल यह एलिमेंट हो, और फिर उसे मूल हीप से मर्ज करने से होता है। मर्ज के कारण, एकल इंजेक्शन का समय होता है। हालांकि, इसे एक मर्ज प्रक्रिया का उपयोग करके तेज़ किया जा सकता है जो मर्ज के एक बिंदु तक पहुंचते ही मर्ज को शॉर्टकट करता है जहां मर्ज होने वाले दोनों हीप्स में से केवल एक में अधिक ऑर्डर के ट्री हैं। इस स्पीडअप के साथ, लगातार प्रविष्टियों की एक श्रृंखला में, प्रविष्टियों के लिए कुल समय है। इसे बताने का एक और तरीका यह है कि (किसी क्रम में पहली इंसर्शन के लिए लघुगणकीय ओवरहेड के बाद) प्रत्येक क्रमिक इन्सर्ट में प्रति इंसर्शन (अर्थात स्थिरांक) का परिशोधन समय होता है।[1][3]
बाइनोमियल हीप का विशेषक रूप, स्क्यू बाइनोमियल हीप, स्क्यू बाइनरी संख्या प्रणाली पर आधारित ट्रीज का उपयोग करके निरंतर खराब गिनती वाला इंजेक्शन समय प्राप्त करता है।[4]
फाइंड मिनिमम
हीप के मिनिमम एलिमेंट को खोजने के लिए, बाइनोमियल ट्रीज की रूट में से मिनिमम एलिमेंट को खोजें। इसे समय में किया जा सकता है, क्योंकि केवल ट्री रूट हैं जिन्हें जांचा जा सकता है।[1]
मिनिमम एलिमेंट वाले बायनोमिअल ट्री के लिए एक सूचक का उपयोग करके, इस ऑपरेशन के लिए समय को तक कम किया जा सकता है। मिनिमम खोजने के अलावा किसी भी ऑपरेशन को निष्पादित करते समय सूचक को अद्यतन किया जाना चाहिए। यह किसी भी ऑपरेशन के समग्र एसिम्प्टोटिक रनिंग समय को बढ़ाए बिना, प्रति अपडेट बार में किया जा सकता है।[citation needed]
डिलीट मिनिमम
हीप से मिनिमम एलिमेंट को डिलीट करने के लिए, सबसे पहले इस एलिमेंट को खोजें, इसे इसके बाइनोमियल ट्री के रूट से हटा दें, और इसके बच्चों के सबट्रीज की एक सूची प्राप्त करें (जो प्रत्येक अलग-अलग ऑर्डर के बाइनोमियल ट्री होते हैं)। इन सबट्रीज की सूची को छोटे से बड़े ऑर्डर तक पुनर्व्यवस्थित करके एक अलग बाइनोमियल हीप में परिवर्तित करें। फिर इस हीप को मूल हीप के साथ मर्ज करें। क्योंकि प्रत्येक रूट में अधिकतम चाइल्ड होते हैं, इस नए हीप को बनाने में समय लगता है। हीप को मर्ज करने में समय लगता है, इसलिए पूरा मिनिमम डिलीट करने ऑपरेशन का समय लगता है।[1]
function deleteMin(heap)
min = heap.trees().first()
for each current in heap.trees()
if current.root < min.root then min = current
for each tree in min.subTrees()
tmp.addTree(tree)
heap.removeTree(min)
merge(heap, tmp)
डिक्रीज कुंजी
एक एलिमेंट की कुंजी को कम करने के बाद, यह अपने पैरेंट की कुंजी से छोटा हो सकता है, जिससे मिनिमम-हीप गुणवत्ता को उल्लंघन किया जाता है। यदि ऐसा है, तो एलिमेंट को अपने पैरेंट के साथ विनिमय करें, और शायद इसके साथ ही उसके ग्रैंडपेरेंट और आगे भी, जब तक मिनिमम-हीप गुणवत्ता का उल्लंघन नहीं होता है। प्रत्येक बाइनोमियल ट्री की ऊंचाई अधिकतम होती है, इसलिए इसके लिए समय लगता है।[1] हालांकि, यह ऑपरेशन यह भी आवश्यक करता है कि ट्री का प्रतिनिधि उसके पैरेंट से पॉइंटर्स को इन्सर्ट, जिससे अन्य ऑपरेशनों के अंगीकरण को कुछ प्रकार से जटिल किया जाता है।[3]
डिलीट
हीप से एक एलिमेंट को डिलीट करने के लिए, इसकी कुंजी को नकारात्मक अविन्फिनिटी (या समतुल्य रूप से, हीप में किसी भी एलिमेंट से कम मान) करें और फिर हीप में मिनिमम एलिमेंट को हटा दें।[1]
अनुप्रयोग
- डिस्क्रीट इवेंट सिमुलेशन
- प्रायोरिटी क्यू
यह भी देखें
- वीक हीप, बाइनरी हीप और बाइनोमियल हीप डेटा स्ट्रक्चरओं का एक संयोजन है।
संदर्भ
- ↑ 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 1.12 1.13 1.14 1.15 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Chapter 19: Binomial Heaps". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 455–475. ISBN 0-262-03293-7.
- ↑ Vuillemin, Jean (1 April 1978). "प्राथमिकता कतारों में हेरफेर करने के लिए एक डेटा संरचना". Communications of the ACM. 21 (4): 309–315. doi:10.1145/359460.359478.
- ↑ 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 Brown, Mark R. (1978). "द्विपद कतार एल्गोरिदम का कार्यान्वयन और विश्लेषण". SIAM Journal on Computing. 7 (3): 298–319. doi:10.1137/0207026. MR 0483830.
- ↑ Brodal, Gerth Stølting; Okasaki, Chris (November 1996), "Optimal purely functional priority queues", Journal of Functional Programming, 6 (6): 839–857, doi:10.1017/s095679680000201x
बाहरी संबंध
- Two C implementations of binomial heap (a generic one and one optimized for integer कुंजियाँ)
- Haskell implementation of binomial heap
- Common Lisp implementation of binomial heap
