द्विपद हीप: Difference between revisions

Revision as of 23:16, 23 July 2023

कंप्यूटर विज्ञान में, एक बिनोमियल हीप एक डेटा संरचना है जो प्राथमिकता कतार के रूप में कार्य करती है लेकिन साथ ही बिनोमियल हीपों के जोड़े जा सकते हैं। यह मर्ज़ किए जा सकने वाले हीप अभिसारण डेटा प्रकार (जिसे विलय योग्य ढेर भी कहा जाता है) के रूप में एक अमूल्य संरचना है, जिसमें मर्ज़ के ऑपरेशन का समर्थन किया जाता है। यह एक हीप के रूप में प्रदर्शित होता है, जो एक बाइनरी हीप के समान होता है, लेकिन इसमें विशेष तरह का वृक्ष संरचना उपयोग किया जाता है जो बाइनरी हीप्स द्वारा उपयोग किए जाने वाले पूर्ण बाइनरी वृक्षों से भिन्न होता है।^[1] बिनोमियल हीप का आविष्कार 1978 में जीन वुइलेमिन ने किया था।^[1]^[2]

द्विपद ढेर

एक द्विपद ढेर को द्विपद पेड़ों के एक सेट के रूप में कार्यान्वित किया जाता है (एक बाइनरी ढेर के साथ तुलना करें, जिसमें एक एकल बाइनरी पेड़ का आकार होता है), जिन्हें निम्नानुसार पुनरावर्ती रूप से परिभाषित किया गया है:^[1]

ऑर्डर 0 का एक द्विपद वृक्ष एक एकल नोड है
क्रम $k$ के एक द्विपद वृक्ष में एक जड़ नोड होता है जिसकी संतानें क्रम $k-1$ , $k-2$ , ..., 2, 1, 0 (इस क्रम में) के द्विपद वृक्षों की जड़ें होती हैं।

0 से 3 क्रम के द्विपद वृक्ष: प्रत्येक वृक्ष में सभी निचले क्रम वाले द्विपद वृक्षों के उपवृक्षों के साथ एक जड़ नोड होता है, जिसे हाइलाइट किया गया है। उदाहरण के लिए, क्रम 3 द्विपद वृक्ष क्रम 2, 1, और 0 (क्रमशः नीले, हरे और लाल के रूप में हाइलाइट किया गया) द्विपद वृक्ष से जुड़ा है।

क्रम $k$ के एक द्विपद वृक्ष में $2^{k}$ नोड्स हैं, और ऊंचाई $k$ है। नाम आकार से आता है: क्रम $k$ के एक द्विपद वृक्ष में गहराई $d$ पर ${\tbinom {k}{d}}$ नोड्स हैं, जो एक द्विपद गुणांक है। इसकी संरचना के कारण, क्रम $k$ के एक द्विपद वृक्ष का निर्माण क्रम $k-1$ के दो पेड़ों से किया जा सकता है, उनमें से एक को दूसरे पेड़ की जड़ के सबसे बाएं बच्चे के रूप में जोड़ा जा सकता है। यह सुविधा द्विपद ढेर के मर्ज ऑपरेशन के लिए केंद्रीय है, जो अन्य पारंपरिक ढेरों की तुलना में इसका प्रमुख लाभ है।^[1]^[3]

द्विपद ढेर की संरचना

एक द्विपद ढेर को द्विपद पेड़ों के एक सेट के रूप में लागू किया जाता है जो द्विपद ढेर गुणों को संतुष्ट करता है:^[1]

ढेर में प्रत्येक द्विपद वृक्ष न्यूनतम-ढेर संपत्ति का पालन करता है: एक नोड की कुंजी उसके मूल की कुंजी से बड़ी या उसके बराबर होती है।
प्रत्येक क्रम के लिए, शून्य क्रम सहित, अधिकतम एक द्विपद वृक्ष हो सकता है।

पहली संपत्ति यह सुनिश्चित करती है कि प्रत्येक द्विपद वृक्ष की जड़ में वृक्ष की सबसे छोटी कुंजी शामिल है। इसका मतलब यह है कि पूरे ढेर में सबसे छोटी कुंजी जड़ों में से एक है।^[1]

एक द्विपद ढेर को द्विपद पेड़ों के एक सेट के रूप में कार्यान्वित किया जाता है जो द्विपद ढेर गुणों को संतुष्ट करते हैं:* ढेर में प्रत्येक द्विपद वृक्ष का पालन करता है: एक नोड की कुंजी उसके मूल की कुंजी से बड़ी या उसके बराबर होती है।

दूसरी संपत्ति का तात्पर्य है कि $n$ नोड्स वाले एक द्विपद ढेर में अधिकतम $1+\log _{2}n$ द्विपद पेड़ होते हैं, जहां $\log _{2}$ द्विपद लघुगणक है। इन पेड़ों की संख्या और क्रम विशिष्ट रूप से नोड्स $n$ की संख्या से निर्धारित होते हैं: संख्या $n$ के द्विआधारी प्रतिनिधित्व में प्रत्येक गैर-शून्य बिट के लिए एक द्विपद पेड़ होता है। उदाहरण के लिए, दशमलव संख्या 13 बाइनरी में 1101 है, $2^{3}+2^{2}+2^{0}$ , और इस प्रकार 13 नोड्स वाले एक द्विपद ढेर में क्रम 3, 2, और 0 के तीन द्विपद पेड़ शामिल होंगे (नीचे चित्र देखें)।^[1]^[3]

विभिन्न तरीकों की संख्या $n$ अलग-अलग कुंजियों वाली वस्तुओं को सबसे बड़े विषम भाजक के बराबर द्विपद ढेर में व्यवस्थित किया जा सकता है $n!$ . के लिए $n=1,2,3,\dots$ ये संख्याएं हैं

विभिन्न कुंजियों वाली $n$ 11 वस्तुओं को एक द्विपद ढेर में व्यवस्थित करने के विभिन्न तरीकों की संख्या $n!$ के सबसे बड़े विषम भाजक के बराबर होती है। 33 के लिए ये संख्याएँ हैं

1, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, ... (sequence A049606 in the OEIS)

यदि 11 वस्तुओं को समान रूप से यादृच्छिक क्रम में द्विपद ढेर में डाला जाता है, तो इनमें से प्रत्येक व्यवस्था समान रूप से संभावित है।^[3]

कार्यान्वयन

क्योंकि किसी भी ऑपरेशन के लिए द्विपद वृक्षों के मूल नोड्स तक यादृच्छिक पहुंच की आवश्यकता नहीं होती है, द्विपद वृक्षों की जड़ों को वृक्ष के बढ़ते क्रम के अनुसार एक लिंक की गई सूची में संग्रहीत किया जा सकता है। चूँकि प्रत्येक नोड के लिए बच्चों की संख्या परिवर्तनशील है, इसलिए प्रत्येक नोड के लिए अपने प्रत्येक बच्चे के लिए अलग-अलग लिंक रखना अच्छी तरह से काम नहीं करता है, जैसा कि एक बाइनरी ट्री में आम होगा; इसके बजाय, प्रत्येक नोड से पेड़ में उसके उच्चतम-क्रम वाले बच्चे और उससे अगले छोटे क्रम के उसके भाई-बहन के लिंक का उपयोग करके इस पेड़ को लागू करना संभव है। इन सिबलिंग पॉइंटर्स को प्रत्येक नोड के बच्चों की लिंक की गई सूची में अगले पॉइंटर्स के रूप में व्याख्या किया जा सकता है, लेकिन जड़ों की लिंक की गई सूची से विपरीत क्रम के साथ: सबसे बड़े से सबसे छोटे क्रम के बजाय, इसके विपरीत। यह प्रतिनिधित्व एक ही क्रम के दो पेड़ों को एक साथ जोड़ने की अनुमति देता है, जिससे निरंतर समय में अगले बड़े क्रम का पेड़ बनता है।

मर्ज

एक ही क्रम के दो द्विपद वृक्षों को मर्ज करने के लिए, पहले रूट कुंजी की तुलना करें। 7>3 के बाद से, बाईं ओर का काला पेड़ (रूट नोड 7 के साथ) दाईं ओर के भूरे पेड़ से (रूट नोड 3 के साथ) एक उपवृक्ष के रूप में जुड़ा हुआ है। परिणाम क्रम 3 का एक पेड़ है।

दो ढेरों को मर्ज करने के ऑपरेशन का उपयोग अधिकांश अन्य ऑपरेशनों में सबरूटीन के रूप में किया जाता है।

इस प्रक्रिया के अंतर्गत एक बुनियादी सबरूटीन एक ही क्रम के द्विपद वृक्षों के जोड़े को मिलाता है। यह दो पेड़ों की जड़ों की कुंजियों (दोनों पेड़ों की सबसे छोटी कुंजियाँ) की तुलना करके किया जा सकता है। बड़ी कुंजी वाले रूट नोड को छोटी कुंजी वाले रूट नोड के चाइल्ड में बनाया जाता है, जिससे उसका क्रम एक बढ़ जाता है:^[1]^[3]

फ़ंक्शन मर्जट्री (पी, क्यू);

    यदि p.root.key <= q.root.key
        वापसी पी . addSubTree ( q )
    अन्य
        वापसी क्यू . addSubTree (पी)

यह दो द्विपद ढेरों के विलय को दर्शाता है। यह एक ही क्रम के दो द्विपद वृक्षों को एक-एक करके विलय करके पूरा किया जाता है। यदि परिणामी विलयित वृक्ष का क्रम दो ढेरों में से एक में एक द्विपद वृक्ष के समान है, तो उन दोनों को फिर से विलय कर दिया जाता है।

दो ढेरों को अधिक सामान्यतः मर्ज करने के लिए, दोनों ढेरों की जड़ों की सूचियों को मर्ज एल्गोरिथ्म के समान तरीके से एक साथ ट्रैवर्स किया जाता है,

पेड़ों के छोटे क्रम से लेकर बड़े क्रम तक के क्रम में। जब विलय किए जा रहे दो ढेरों में से केवल एक में ऑर्डर का पेड़ होता है $j$ , इस पेड़ को आउटपुट हीप में ले जाया जाता है। जब दोनों ढेरों में क्रम का एक वृक्ष हो $j$ , दो वृक्ष क्रम के एक वृक्ष में विलीन हो जाते हैं $j+1$ ताकि न्यूनतम-ढेर संपत्ति संतुष्ट हो। बाद में इस वृक्ष को किसी अन्य क्रम के वृक्ष के साथ मिलाना आवश्यक हो सकता है $j+1$ दो इनपुट ढेरों में से एक में। एल्गोरिदम के दौरान, यह किसी भी क्रम के अधिकतम तीन पेड़ों की जांच करेगा, दो ढेरों में से दो जिन्हें हम मिलाते हैं और एक दो छोटे पेड़ों से बना है।^[1]^[3]

फ़ंक्शन मर्ज (पी, क्यू)

    जबकि नहीं (p.end() और q.end())
        पेड़ = मर्जट्री(p.currentTree(), q.currentTree())

        यदि ढेर नहीं है.currentTree().empty()
            पेड़ = मर्जट्री(पेड़, ढेर.करंटट्री())

        heap.addTree(वृक्ष)
        ढेर.अगला(); पी.अगला(); q.अगला()

चूँकि एक द्विपद ढेर में प्रत्येक द्विपद वृक्ष अपने आकार के द्विआधारी प्रतिनिधित्व में एक बिट से मेल खाता है, दो ढेरों के विलय और दो ढेरों के आकार के द्विआधारी जोड़ के बीच एक सादृश्य है, दाएँ से लेकर -बाएं। जब भी जोड़ के दौरान कोई स्थानांतरण होता है, तो यह विलय के दौरान दो द्विपद वृक्षों के विलय से मेल खाता है।^[1]^[3]

विलय के दौरान प्रत्येक द्विपद वृक्ष ट्रैवर्सल में केवल जड़ें शामिल होती हैं, इसलिए समय अधिकतम क्रम में लगता है $\log _{2}n$ और इसलिए चलने का समय है $O(\log n)$ .^[1]^[3]

सम्मिलित करें

एक ढेर में एक नया तत्व सम्मिलित करना केवल इस तत्व से युक्त एक नया ढेर बनाकर और फिर इसे मूल ढेर के साथ विलय करके किया जा सकता है। मर्ज के कारण, एक प्रविष्टि में समय लगता है $O(\log n)$ . हालाँकि, मर्ज प्रक्रिया का उपयोग करके इसे तेज किया जा सकता है जो उस बिंदु तक पहुंचने के बाद मर्ज को शॉर्टकट करता है जहां मर्ज किए गए ढेरों में से केवल एक में बड़े क्रम के पेड़ होते हैं। इस गति के साथ, की एक श्रृंखला में $k$ लगातार सम्मिलन, सम्मिलन के लिए कुल समय है $O(k+\log n)$ . इसे बताने का दूसरा तरीका यह है कि (किसी अनुक्रम में पहली प्रविष्टि के लिए लॉगरिदमिक ओवरहेड के बाद) प्रत्येक क्रमिक प्रविष्टि में एक परिशोधन समय होता है|परिशोधन समय $O(1)$ (अर्थात् स्थिरांक) प्रति प्रविष्टि।^[1]^[3]

द्विपद ढेर का एक प्रकार, तिरछा द्विपद ढेर, वनों का उपयोग करके निरंतर सबसे खराब स्थिति सम्मिलन समय प्राप्त करता है जिनके पेड़ का आकार द्विआधारी संख्या प्रणाली के बजाय तिरछी द्विआधारी संख्या प्रणाली पर आधारित होता है।^[4]

न्यूनतम ज्ञात कीजिए

ढेर का न्यूनतम तत्व ज्ञात करने के लिए, द्विपद वृक्षों की जड़ों में से न्यूनतम तत्व ज्ञात करें। इसमें किया जा सकता है $O(\log n)$ समय, जैसा कि अभी है $O(\log n)$ जांचने के लिए पेड़ की जड़ें।^[1]

न्यूनतम तत्व वाले द्विपद वृक्ष के लिए एक सूचक का उपयोग करके, इस ऑपरेशन के समय को कम किया जा सकता है $O(1)$ . न्यूनतम खोजने के अलावा कोई भी ऑपरेशन करते समय पॉइंटर को अपडेट किया जाना चाहिए। इसमें किया जा सकता है $O(\log n)$ प्रति अद्यतन समय, किसी भी ऑपरेशन के समग्र एसिम्प्टोटिक रनिंग समय को बढ़ाए बिना।^{[citation needed]}

न्यूनतम हटाएं

ढेर से न्यूनतम तत्व को हटाने के लिए, पहले इस तत्व को ढूंढें, इसे इसके द्विपद वृक्ष की जड़ से हटा दें, और इसके उप-वृक्षों की एक सूची प्राप्त करें (जो प्रत्येक स्वयं अलग-अलग क्रम के द्विपद वृक्ष हैं)। उपवृक्षों की इस सूची को सबसे छोटे से सबसे बड़े क्रम में पुन: व्यवस्थित करके एक अलग द्विपद ढेर में बदलें। फिर इस ढेर को मूल ढेर के साथ मिला दें। चूँकि प्रत्येक जड़ में अधिकतम होता है $\log _{2}n$ बच्चों, इस नए ढेर को बनाने में समय लगता है $O(\log n)$ . ढेरों को मिलाने में समय लगता है $O(\log n)$ , इसलिए संपूर्ण डिलीट न्यूनतम ऑपरेशन में समय लगता है $O(\log n)$ .^[1]

फ़ंक्शन डिलीटमिन (ढेर)

    मिनट = ढेर.पेड़().पहला()
    heap.trees() में प्रत्येक धारा के लिए
        यदि current.root < min.root तो min = current
    min.subTrees() में प्रत्येक पेड़ के लिए
        tmp.addTree(वृक्ष)
    ढेर.निकालेंपेड़(मिनट)
    मर्ज (ढेर, टीएमपी)

कुंजी घटाएं

किसी तत्व की कुंजी कम करने के बाद, यह न्यूनतम-ढेर संपत्ति का उल्लंघन करते हुए, अपने मूल की कुंजी से छोटा हो सकता है। यदि यह मामला है, तो तत्व को उसके माता-पिता के साथ बदलें, और संभवतः उसके दादा-दादी के साथ भी, और इसी तरह, जब तक कि न्यूनतम-ढेर संपत्ति का उल्लंघन न हो जाए। प्रत्येक द्विपद वृक्ष की ऊँचाई अधिकतम होती है $\log _{2}n$ , तो यह लेता है $O(\log n)$ समय।^[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 keys)
Haskell implementation of binomial heap
Common Lisp implementation of binomial heap

[clrs-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.

[2] Vuillemin, Jean (1 April 1978). "प्राथमिकता कतारों में हेरफेर करने के लिए एक डेटा संरचना". Communications of the ACM. 21 (4): 309–315. doi:10.1145/359460.359478.

[brown-3] 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.

[4] 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

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
-{{Use dmy dates|date=May 2018}}
 {{redirect|Binomial tree|binomial price trees|binomial options pricing model}}
-[[कंप्यूटर विज्ञान]] में, द्विपद ढेर एक [[डेटा संरचना]] है जो [[प्राथमिकता कतार]] के रूप में कार्य करती है लेकिन ढेर के जोड़े को विलय करने की भी अनुमति देती है।
+[[कंप्यूटर विज्ञान]] में, एक बिनोमियल हीप एक [[डेटा संरचना]] है जो [[प्राथमिकता कतार]] के रूप में कार्य करती है लेकिन साथ ही [[पिघलने योग्य ढेर|बिनोमियल हीपों]] के जोड़े जा सकते हैं। यह मर्ज़ किए जा सकने वाले हीप [[अमूर्त डेटा प्रकार|अभिसारण डेटा प्रकार]] (जिसे [[विलय योग्य ढेर]] भी कहा जाता है) के रूप में एक अमूल्य संरचना है, जिसमें मर्ज़ के ऑपरेशन का समर्थन किया जाता है। यह एक हीप के रूप में प्रदर्शित होता है, जो एक [[ बाइनरी ढेर |बाइनरी हीप]] के समान होता है, लेकिन इसमें विशेष तरह का वृक्ष संरचना उपयोग किया जाता है जो बाइनरी हीप्स द्वारा उपयोग किए जाने वाले पूर्ण बाइनरी वृक्षों से भिन्न होता है।<ref name="clrs">{{Introduction to Algorithms |edition=2 |chapter=Chapter 19: Binomial Heaps |pages=455–475}}</ref> बिनोमियल हीप का आविष्कार 1978 में [[जीन वुइलेमिन]] ने किया था।<ref name="clrs" /><ref>{{Cite journal|last=Vuillemin|first=Jean|date=1 April 1978|title=प्राथमिकता कतारों में हेरफेर करने के लिए एक डेटा संरचना|journal=Communications of the ACM|volume=21|issue=4|pages=309–315|doi=10.1145/359460.359478}}</ref>
-यह मर्ज [[पिघलने योग्य ढेर]] [[अमूर्त डेटा प्रकार]] (जिसे [[विलय योग्य ढेर]] भी कहा जाता है) के कार्यान्वयन के रूप में महत्वपूर्ण है, जो मर्ज ऑपरेशन का समर्थन करने वाली प्राथमिकता कतार है। इसे [[ बाइनरी ढेर ]] के समान हीप (डेटा संरचना) के रूप में कार्यान्वित किया जाता है, लेकिन एक विशेष वृक्ष संरचना का उपयोग किया जाता है जो बाइनरी हीप्स द्वारा उपयोग किए जाने वाले पूर्ण बाइनरी पेड़ों से अलग होता है।<ref name=clrs>{{Introduction to Algorithms |edition=2 |chapter=Chapter 19: Binomial Heaps |pages=455–475}}</ref> द्विपद ढेर का आविष्कार 1978 में [[जीन वुइलेमिन]] द्वारा किया गया था।<ref name="clrs" /><ref>{{Cite journal|last=Vuillemin|first=Jean|date=1 April 1978|title=प्राथमिकता कतारों में हेरफेर करने के लिए एक डेटा संरचना|journal=Communications of the ACM|volume=21|issue=4|pages=309–315|doi=10.1145/359460.359478}}</ref>
+== द्विपद ढेर ==
+एक द्विपद ढेर को द्विपद [[वृक्ष डेटा संरचना|पेड़ों]] के एक सेट के रूप में कार्यान्वित किया जाता है (एक बाइनरी ढेर के साथ तुलना करें, जिसमें एक एकल [[द्विआधारी वृक्ष|बाइनरी पेड़]] का आकार होता है), जिन्हें निम्नानुसार पुनरावर्ती रूप से परिभाषित किया गया है:<ref name="clrs" />
+* ऑर्डर 0 का एक द्विपद वृक्ष एक एकल नोड है
+* क्रम <math>k</math> के एक द्विपद वृक्ष में एक जड़ नोड होता है जिसकी संतानें क्रम <math>k-1</math>,  <math>k-2</math>, ..., 2, 1, 0 (इस क्रम में) के द्विपद वृक्षों की जड़ें होती हैं।
-== द्विपद ढेर ==
+[[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" />* क्रम 0 का एक द्विपद वृक्ष एक एकल नोड है
+== द्विपद ढेर की संरचना ==
-* क्रम का एक द्विपद वृक्ष <math>k</math> एक रूट नोड है जिसके बच्चे क्रम के द्विपद वृक्षों की जड़ें हैं <math>k-1</math>, <math>k-2</math>, ..., 2, 1, 0 (इस क्रम में)।
+एक द्विपद ढेर को द्विपद पेड़ों के एक सेट के रूप में लागू किया जाता है जो द्विपद ढेर गुणों को संतुष्ट करता है:<ref name="clrs" />
-[[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>\tbinom k d</math> गहराई पर नोड्स <math>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|अलग-अलग कुंजियों के साथ 13 नोड्स वाले द्विपद ढेर का उदाहरण। ढेर में 0, 2, और 3.|अंगूठे क्रम वाले तीन द्विपद वृक्ष हैं]]विभिन्न तरीकों की संख्या <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}}
+:
-यदि <math>n</math> वस्तुओं को समान रूप से यादृच्छिक क्रम में द्विपद ढेर में डाला जाता है, इनमें से प्रत्येक व्यवस्था समान रूप से संभावित है।<ref name="brown" />
+विभिन्न कुंजियों वाली <math>n</math>11 वस्तुओं को एक द्विपद ढेर में व्यवस्थित करने के विभिन्न तरीकों की संख्या <math>n!</math> के सबसे बड़े विषम भाजक के बराबर होती है। 33 के लिए ये संख्याएँ हैं
+, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, ... {{OEIS|A049606}}
+यदि 11 वस्तुओं को समान रूप से यादृच्छिक क्रम में द्विपद ढेर में डाला जाता है, तो इनमें से प्रत्येक व्यवस्था समान रूप से संभावित है।<ref name="brown" />
 == कार्यान्वयन ==
-क्योंकि किसी भी ऑपरेशन के लिए द्विपद वृक्षों के मूल नोड्स तक यादृच्छिक पहुंच की आवश्यकता नहीं होती है, द्विपद वृक्षों की जड़ों को वृक्ष के बढ़ते क्रम के अनुसार एक लिंक की गई सूची में संग्रहीत किया जा सकता है। चूँकि प्रत्येक नोड के लिए बच्चों की संख्या परिवर्तनशील है, इसलिए प्रत्येक नोड के लिए अपने प्रत्येक बच्चे के लिए अलग-अलग लिंक रखना अच्छी तरह से काम नहीं करता है, जैसा कि एक बाइनरी ट्री में आम होगा; इसके बजाय, प्रत्येक नोड से पेड़ में उसके उच्चतम-क्रम वाले बच्चे और उससे अगले छोटे क्रम के उसके भाई-बहन के लिंक का उपयोग करके इस पेड़ को लागू करना संभव है। इन सिबलिंग पॉइंटर्स को प्रत्येक नोड के बच्चों की लिंक की गई सूची में अगले पॉइंटर्स के रूप में व्याख्या किया जा सकता है, लेकिन जड़ों की लिंक की गई सूची से विपरीत क्रम के साथ: सबसे बड़े से सबसे छोटे क्रम के बजाय, इसके विपरीत। यह प्रतिनिधित्व एक ही क्रम के दो पेड़ों को एक साथ जोड़ने की अनुमति देता है, जिससे निरंतर समय में अगले बड़े क्रम का पेड़ बनता है।<ref name="clrs" /><ref name="brown" />
+== कार्यान्वयन ==
+क्योंकि किसी भी ऑपरेशन के लिए द्विपद वृक्षों के मूल नोड्स तक यादृच्छिक पहुंच की आवश्यकता नहीं होती है, द्विपद वृक्षों की जड़ों को वृक्ष के बढ़ते क्रम के अनुसार एक लिंक की गई सूची में संग्रहीत किया जा सकता है। चूँकि प्रत्येक नोड के लिए बच्चों की संख्या परिवर्तनशील है, इसलिए प्रत्येक नोड के लिए अपने प्रत्येक बच्चे के लिए अलग-अलग लिंक रखना अच्छी तरह से काम नहीं करता है, जैसा कि एक बाइनरी ट्री में आम होगा; इसके बजाय, प्रत्येक नोड से पेड़ में उसके उच्चतम-क्रम वाले बच्चे और उससे अगले छोटे क्रम के उसके भाई-बहन के लिंक का उपयोग करके इस पेड़ को लागू करना संभव है। इन सिबलिंग पॉइंटर्स को प्रत्येक नोड के बच्चों की लिंक की गई सूची में अगले पॉइंटर्स के रूप में व्याख्या किया जा सकता है, लेकिन जड़ों की लिंक की गई सूची से विपरीत क्रम के साथ: सबसे बड़े से सबसे छोटे क्रम के बजाय, इसके विपरीत। यह प्रतिनिधित्व एक ही क्रम के दो पेड़ों को एक साथ जोड़ने की अनुमति देता है, जिससे निरंतर समय में अगले बड़े क्रम का पेड़ बनता है।
 === मर्ज ===
 [[File:Binomial heap merge1.svg|thumb|200px|एक ही क्रम के दो द्विपद वृक्षों को मर्ज करने के लिए, पहले रूट कुंजी की तुलना करें। 7>3 के बाद से, बाईं ओर का काला पेड़ (रूट नोड 7 के साथ) दाईं ओर के भूरे पेड़ से (रूट नोड 3 के साथ) एक उपवृक्ष के रूप में जुड़ा हुआ है। परिणाम क्रम 3 का एक पेड़ है।]]दो ढेरों को मर्ज करने के ऑपरेशन का उपयोग अधिकांश अन्य ऑपरेशनों में सबरूटीन के रूप में किया जाता है।

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

Anonymous

Search

द्विपद हीप: Difference between revisions

Namespaces

More

Page actions

Revision as of 23:16, 23 July 2023

Contents

द्विपद ढेर

द्विपद ढेर की संरचना

कार्यान्वयन

कार्यान्वयन

मर्ज

सम्मिलित करें

न्यूनतम ज्ञात कीजिए

न्यूनतम हटाएं

कुंजी घटाएं

हटाएं

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

द्विपद हीप: Difference between revisions

Revision as of 23:16, 23 July 2023

द्विपद ढेर

द्विपद ढेर की संरचना

कार्यान्वयन

कार्यान्वयन

मर्ज

सम्मिलित करें

न्यूनतम ज्ञात कीजिए

न्यूनतम हटाएं

कुंजी घटाएं

हटाएं

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories