द्विपद हीप

"Binomial tree" redirects here. For binomial price trees, see binomial options pricing model.

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

द्विपद ढेर

एक द्विपद ढेर को द्विपद वृक्ष डेटा संरचना के एक सेट के रूप में कार्यान्वित किया जाता है (द्विआधारी वृक्ष के साथ तुलना करें, जिसमें एकल बाइनरी पेड़ का आकार होता है), जिन्हें निम्नानुसार पुनरावर्ती रूप से परिभाषित किया जाता है:* क्रम 0 का एक द्विपद वृक्ष एक एकल नोड है

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

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

क्रम का एक द्विपद वृक्ष $k$ है $2^{k}$ नोड्स, और ऊंचाई $k$.

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

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

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

• शून्य क्रम सहित प्रत्येक क्रम के लिए अधिकतम एक द्विपद वृक्ष हो सकता है।

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

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

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

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

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

कार्यान्वयन

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

मर्ज

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

कुंजी घटाएं

किसी तत्व की कुंजी कम करने के बाद, यह न्यूनतम-ढेर संपत्ति का उल्लंघन करते हुए, अपने मूल की कुंजी से छोटा हो सकता है। यदि यह मामला है, तो तत्व को उसके माता-पिता के साथ बदलें, और संभवतः उसके दादा-दादी के साथ भी, और इसी तरह, जब तक कि न्यूनतम-ढेर संपत्ति का उल्लंघन न हो जाए। प्रत्येक द्विपद वृक्ष की ऊँचाई अधिकतम होती है $\log _{2}n$, तो यह लेता है $O(\log n)$ समय।हालाँकि, इस ऑपरेशन के लिए आवश्यक है कि पेड़ के प्रतिनिधित्व में पेड़ में प्रत्येक नोड से उसके मूल तक के पॉइंटर्स शामिल हों, जो अन्य ऑपरेशनों के कार्यान्वयन को कुछ हद तक जटिल बनाता है।

हटाएं

ढेर से किसी तत्व को हटाने के लिए, इसकी कुंजी को नकारात्मक अनंत तक कम करें (या समकक्ष, ढेर में किसी भी तत्व से कुछ कम मूल्य तक) और फिर ढेर में न्यूनतम हटा दें।

अनुप्रयोग

• असतत घटना अनुकरण
• प्राथमिकता कतारें

यह भी देखें

• कमजोर ढेर, द्विआधारी ढेर और द्विपद ढेर डेटा संरचनाओं का एक संयोजन

बाहरी संबंध

• 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