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

Latest revision as of 12:35, 28 July 2023

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

बायनोमिअल हीप

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

ऑर्डर 0 का एक बायनोमिअल ट्री एकल नोड होता है
ऑर्डर $k$ के एक बायनोमिअल ट्री में एक रूट नोड होता है जिसके चिल्ड्रन ऑर्डर $k-1$ , $k-2$ , ..., 2, 1, 0 (इस ऑर्डर में) के बायनोमिअल ट्रीज की रूटें होती हैं।

File:Binomial Trees.svg

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$ के लिए ये संख्याएँ हैं

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

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

कार्यान्वयन

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

मर्ज

File:Binomial heap merge1.svg

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

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

   function mergeTree(p, q)   
      if p.root.कुंजी <= q.root.कुंजी
          return p.addSubTree(q)
      else
          return q.addSubTree(p)

File:Binomial heap merge2.svg

यह दो बायनोमिअल हीप्स के विलय को दर्शाता है। यह एक ही ऑर्डर के दो बायनोमिअल ट्रीज को एक-एक करके विलय करके पूरा किया जाता है। यदि परिणामी विलयित ट्री का ऑर्डर दो हीप्स में से एक में एक बायनोमिअल ट्री के समान है, तो उन दोनों को फिर से विलय कर दिया जाता है।

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

विलय के दौरान प्रत्येक बायनोमिअल ट्री के ट्रैवर्सल में केवल रूटें सम्मिलित होती हैं, इसलिए अधिकतम ऑर्डर $\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)$ बार में किया जा सकता है।

डिलीट मिनिमम

हीप से मिनिमम एलिमेंट को डिलीट करने के लिए, सबसे पहले इस एलिमेंट को खोजें, इसे इसके बाइनोमियल ट्री के रूट से हटा दें, और इसके बच्चों के सबट्रीज की एक सूची प्राप्त करें (जो प्रत्येक अलग-अलग ऑर्डर के बाइनोमियल ट्री होते हैं)। इन सबट्रीज की सूची को छोटे से बड़े ऑर्डर तक पुनर्व्यवस्थित करके एक अलग बाइनोमियल हीप में परिवर्तित करें। फिर इस हीप को मूल हीप के साथ मर्ज करें। क्योंकि प्रत्येक रूट में अधिकतम $\log _{2}n$ चाइल्ड होते हैं, इस नए हीप को बनाने में समय $O(\log n)$ लगता है। हीप को मर्ज करने में समय $O(\log n)$ लगता है, इसलिए पूरा मिनिमम डिलीट करने ऑपरेशन का समय $O(\log n)$ लगता है।^[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)

डिक्रीज कुंजी

एक एलिमेंट की कुंजी को कम करने के बाद, यह अपने पैरेंट की कुंजी से छोटा हो सकता है, जिससे मिनिमम-हीप गुणवत्ता को उल्लंघन किया जाता है। यदि ऐसा है, तो एलिमेंट को अपने पैरेंट के साथ विनिमय करें, और शायद इसके साथ ही उसके ग्रैंडपेरेंट और आगे भी, जब तक मिनिमम-हीप गुणवत्ता का उल्लंघन नहीं होता है। प्रत्येक बाइनोमियल ट्री की ऊंचाई अधिकतम $\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 कुंजियाँ)
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|बायनोमिअल ट्री|बायनोमिअल प्राइस ट्री|बायनोमिअल ऑप्शन प्राइसिंग मॉडल}}
-{{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> ये संख्याएं हैं
+[[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}}
-यदि <math>n</math> वस्तुओं को समान रूप से यादृच्छिक क्रम में द्विपद ढेर में डाला जाता है, इनमें से प्रत्येक व्यवस्था समान रूप से संभावित है।<ref name="brown" />
+यदि 11 वस्तुओं को समान रूप से यादृच्छिक ऑर्डर में बायनोमिअल हीप में डाला जाता है, तो इनमें से प्रत्येक व्यवस्था समान रूप से संभावित है।<ref name="brown" />
 == कार्यान्वयन ==
-क्योंकि किसी भी ऑपरेशन के लिए द्विपद वृक्षों के मूल नोड्स तक यादृच्छिक पहुंच की आवश्यकता नहीं होती है, द्विपद वृक्षों की जड़ों को वृक्ष के बढ़ते क्रम के अनुसार एक लिंक की गई सूची में संग्रहीत किया जा सकता है। चूँकि प्रत्येक नोड के लिए बच्चों की संख्या परिवर्तनशील है, इसलिए प्रत्येक नोड के लिए अपने प्रत्येक बच्चे के लिए अलग-अलग लिंक रखना अच्छी तरह से काम नहीं करता है, जैसा कि एक बाइनरी ट्री में आम होगा; इसके बजाय, प्रत्येक नोड से पेड़ में उसके उच्चतम-क्रम वाले बच्चे और उससे अगले छोटे क्रम के उसके भाई-बहन के लिंक का उपयोग करके इस पेड़ को लागू करना संभव है। इन सिबलिंग पॉइंटर्स को प्रत्येक नोड के बच्चों की लिंक की गई सूची में अगले पॉइंटर्स के रूप में व्याख्या किया जा सकता है, लेकिन जड़ों की लिंक की गई सूची से विपरीत क्रम के साथ: सबसे बड़े से सबसे छोटे क्रम के बजाय, इसके विपरीत। यह प्रतिनिधित्व एक ही क्रम के दो पेड़ों को एक साथ जोड़ने की अनुमति देता है, जिससे निरंतर समय में अगले बड़े क्रम का पेड़ बनता है।<ref name="clrs" /><ref name="brown" />
+क्योंकि किसी भी ऑपरेशन के लिए बायनोमिअल ट्रीज के मूल नोड्स तक यादृच्छिक पहुंच की आवश्यकता नहीं होती है, बायनोमिअल ट्रीज की रूट्स को ट्री के बढ़ते ऑर्डर के अनुसार एक लिंक की गई सूची में संग्रहीत किया जा सकता है। चूँकि प्रत्येक नोड के लिए बच्चों की संख्या परिवर्तनशील है, इसलिए प्रत्येक नोड के लिए अपने प्रत्येक चाइल्ड के लिए अलग-अलग लिंक रखना अच्छी तरह से काम नहीं करता है, जैसा कि एक बाइनरी ट्री में आम होगा; इसके बजाय, प्रत्येक नोड से ट्री में उसके उच्चतम-ऑर्डर वाले चाइल्ड और उससे अगले छोटे ऑर्डर के उसके भाई-बहन के लिंक का उपयोग करके इस ट्री को लागू करना संभव है। इन सिबलिंग पॉइंटर्स को प्रत्येक नोड के बच्चों की लिंक की गई सूची में अगले पॉइंटर्स के रूप में व्याख्या किया जा सकता है, लेकिन रूट्स की लिंक की गई सूची से विपरीत ऑर्डर के साथ: सबसे बड़े से सबसे छोटे ऑर्डर के बजाय, इसके विपरीत। यह प्रतिनिधित्व एक ही ऑर्डर के दो ट्रीज को एक साथ जोड़ने की अनुमति देता है, जिससे निरंतर समय में अगले बड़े ऑर्डर का ट्री बनता है।
 === मर्ज ===
-[[File:Binomial heap merge1.svg|thumb|200px|एक ही क्रम के दो द्विपद वृक्षों को मर्ज करने के लिए, पहले रूट कुंजी की तुलना करें। 7>3 के बाद से, बाईं ओर का काला पेड़ (रूट नोड 7 के साथ) दाईं ओर के भूरे पेड़ से (रूट नोड 3 के साथ) एक उपवृक्ष के रूप में जुड़ा हुआ है। परिणाम क्रम 3 का एक पेड़ है।]]दो ढेरों को मर्ज करने के ऑपरेशन का उपयोग अधिकांश अन्य ऑपरेशनों में सबरूटीन के रूप में किया जाता है।
+[[File:Binomial heap merge1.svg|thumb|200px|एक ही ऑर्डर के दो बायनोमिअल ट्रीज को मर्ज करने के लिए, पहले रूट कुंजी की तुलना करें। 7>3 के बाद से, बाईं ओर का काला ट्री (रूट नोड 7 के साथ) दाईं ओर के भूरे ट्री से (रूट नोड 3 के साथ) एक सबट्री के रूप में जुड़ा हुआ है। परिणाम ऑर्डर 3 का एक ट्री है।]]दो हीप्स को '''मर्जिंग''' का ऑपरेशन को अधिकांश अन्य ऑपरेशनों में एक सबरूटीन के रूप में उपयोग किया जाता है। इस प्रक्रिया के भीतर एक मूल सबरूटीन, एक ही ऑर्डर के बाइनोमियल ट्री के जोड़ा बनाने के लिए उपयोग किया जाता है। इसे दो ट्री के रूट्स पर मौजूद कुंजियाँ की तुलना करके किया जा सकता है (दोनों ट्री में सबसे छोटी कुंजियाँ)। बड़े कुंजी वाले रूट नोड को छोटे कुंजी वाले रूट नोड का एक चाइल्ड बनाया जाता है, जिससे उसका ऑर्डर एक के साथ बढ़ जाता है:<ref name="clrs" /><ref name="brown" />
-इस प्रक्रिया के अंतर्गत एक बुनियादी सबरूटीन एक ही क्रम के द्विपद वृक्षों के जोड़े को मिलाता है। यह दो पेड़ों की जड़ों की कुंजियों (दोनों पेड़ों की सबसे छोटी कुंजियाँ) की तुलना करके किया जा सकता है। बड़ी कुंजी वाले रूट नोड को छोटी कुंजी वाले रूट नोड के चाइल्ड में बनाया जाता है, जिससे उसका क्रम एक बढ़ जाता है:<ref name="clrs" /><ref name="brown" />
+    '''function''' mergeTree(p, q)
+       '''if''' p.root.कुंजी <= q.root.कुंजी
-फ़ंक्शन मर्जट्री (पी, क्यू);
+           '''return''' p.addSubTree(q)
-     यदि p.root.key <= q.root.key
+       '''else'''
-         वापसी पी . addSubTree ( q )
+           '''return''' q.addSubTree(p)
-     अन्य
-         वापसी क्यू . addSubTree (पी)
-[[File:Binomial heap merge2.svg|thumb|300px|यह दो द्विपद ढेरों के विलय को दर्शाता है। यह एक ही क्रम के दो द्विपद वृक्षों को एक-एक करके विलय करके पूरा किया जाता है। यदि परिणामी विलयित वृक्ष का क्रम दो ढेरों में से एक में एक द्विपद वृक्ष के समान है, तो उन दोनों को फिर से विलय कर दिया जाता है।]]दो ढेरों को अधिक सामान्यतः मर्ज करने के लिए, दोनों ढेरों की जड़ों की सूचियों को [[मर्ज एल्गोरिथ्म]] के समान तरीके से एक साथ ट्रैवर्स किया जाता है,
-पेड़ों के छोटे क्रम से लेकर बड़े क्रम तक के क्रम में। जब विलय किए जा रहे दो ढेरों में से केवल एक में ऑर्डर का पेड़ होता है <math>j</math>, इस पेड़ को आउटपुट हीप में ले जाया जाता है। जब दोनों ढेरों में क्रम का एक वृक्ष हो <math>j</math>, दो वृक्ष क्रम के एक वृक्ष में विलीन हो जाते हैं <math>j+1</math> ताकि न्यूनतम-ढेर संपत्ति संतुष्ट हो। बाद में इस वृक्ष को किसी अन्य क्रम के वृक्ष के साथ मिलाना आवश्यक हो सकता है <math>j+1</math> दो इनपुट ढेरों में से एक में। एल्गोरिदम के दौरान, यह किसी भी क्रम के अधिकतम तीन पेड़ों की जांच करेगा, दो ढेरों में से दो जिन्हें हम मिलाते हैं और एक दो छोटे पेड़ों से बना है।<ref name="clrs" /><ref name="brown" />
-फ़ंक्शन मर्ज (पी, क्यू)
-     जबकि नहीं (p.end() और q.end())
-         पेड़ = मर्जट्री(p.currentTree(), q.currentTree())
-         यदि ढेर नहीं है.currentTree().empty()
-             पेड़ = मर्जट्री(पेड़, ढेर.करंटट्री())
-         heap.addTree(वृक्ष)
+[[File:Binomial heap merge2.svg|thumb|300px|यह दो बायनोमिअल हीप्स के विलय को दर्शाता है। यह एक ही ऑर्डर के दो बायनोमिअल ट्रीज को एक-एक करके विलय करके पूरा किया जाता है। यदि परिणामी विलयित ट्री का ऑर्डर दो हीप्स में से एक में एक बायनोमिअल ट्री के समान है, तो उन दोनों को फिर से विलय कर दिया जाता है।]]दो हीप्स को अधिक सामान्यतः मर्ज करने के लिए, दोनों हीप्स की रूट्स की सूचियों को [[मर्ज एल्गोरिथ्म]] के समान तरीके से एक साथ, ट्रीज के छोटे ऑर्डर से बड़े ऑर्डर तक के ऑर्डर में ट्रेस किया जाता है। जब विलय किए जा रहे दो हीप्स में से केवल एक में ऑर्डर <math>j</math> का ट्री होता है, तो इस ट्री को आउटपुट हीप में ले जाया जाता है। जब दोनों हीप्स में ऑर्डर <math>j</math> का एक ट्री होता है, तो दोनों ट्रीज को ऑर्डर <math>j+1</math> के एक ट्री में मिला दिया जाता है ताकि मिनिमम-हीप गुणधर्म संतुष्ट हो। बाद में इस ट्री को दो इनपुट हीप्स में से किसी एक में ऑर्डर <math>j+1</math> के किसी अन्य ट्री के साथ विलय करना आवश्यक हो सकता है। एल्गोरिदम के दौरान, यह किसी भी ऑर्डर के अधिकतम तीन ट्रीज की जांच करेगा, दो हीप्स में से दो जिन्हें हम मिलाते हैं और एक दो छोटे ट्रीज से बना है।<ref name="clrs" /><ref name="brown" />
-         ढेर.अगला(); पी.अगला(); q.अगला()
+  '''function''' merge(p, q)
+     '''while''' '''not''' (p.end() '''and''' q.end())
+         tree = mergeTree(p.currentTree(), q.currentTree())
-चूँकि एक द्विपद ढेर में प्रत्येक द्विपद वृक्ष अपने आकार के द्विआधारी प्रतिनिधित्व में एक बिट से मेल खाता है, दो ढेरों के विलय और दो ढेरों के ''आकार'' के द्विआधारी जोड़ के बीच एक सादृश्य है, दाएँ से लेकर -बाएं। जब भी जोड़ के दौरान कोई स्थानांतरण होता है, तो यह विलय के दौरान दो द्विपद वृक्षों के विलय से मेल खाता है।<ref name="clrs" /><ref name="brown" />
+         '''if''' '''not''' heap.currentTree().empty()
+             tree = mergeTree(tree, heap.currentTree())
-विलय के दौरान प्रत्येक द्विपद वृक्ष ट्रैवर्सल में केवल जड़ें शामिल होती हैं, इसलिए समय अधिकतम क्रम में लगता है <math>\log_2 n</math> और इसलिए चलने का समय है <math>O(\log n)</math>.<ref name="clrs" /><ref name="brown" />
+         heap.addTree(tree)
+         heap.next(); p.next(); q.next()
+क्योंकि बायनोमिअल हीप में प्रत्येक बायनोमिअल ट्री अपने साइज के बाइनरी प्रतिनिधित्व में एक बिट से मेल खाता है, दो हीप्स के विलय और दाएं से बाएं तक दो हीप्स के ''साइज'' के बाइनरी जोड़ के बीच एक समानता है। जब भी जोड़ के दौरान कोई स्थानांतरण होता है, तो यह विलय के दौरान दो बायनोमिअल ट्रीज के विलय से मेल खाता है।<ref name="clrs" /><ref name="brown" />
+विलय के दौरान प्रत्येक बायनोमिअल ट्री के ट्रैवर्सल में केवल रूटें सम्मिलित होती हैं, इसलिए अधिकतम ऑर्डर <math>\log_2 n</math> पर लगने वाला समय बनता है और इसलिए रनिंग टाइम <math>O(\log n)</math> होता है।<ref name="clrs" /><ref name="brown" />
-=== सम्मिलित करें ===
+=== इन्सर्ट ===
-एक ढेर में एक नया तत्व सम्मिलित करना केवल इस तत्व से युक्त एक नया ढेर बनाकर और फिर इसे मूल ढेर के साथ विलय करके किया जा सकता है। मर्ज के कारण, एक प्रविष्टि में समय लगता है <math>O(\log n)</math>. हालाँकि, मर्ज प्रक्रिया का उपयोग करके इसे तेज किया जा सकता है जो उस बिंदु तक पहुंचने के बाद मर्ज को शॉर्टकट करता है जहां मर्ज किए गए ढेरों में से केवल एक में बड़े क्रम के पेड़ होते हैं। इस गति के साथ, की एक श्रृंखला में <math>k</math> लगातार सम्मिलन, सम्मिलन के लिए कुल समय है <math>O(k+\log n)</math>. इसे बताने का दूसरा तरीका यह है कि (किसी अनुक्रम में पहली प्रविष्टि के लिए लॉगरिदमिक ओवरहेड के बाद) प्रत्येक क्रमिक प्रविष्टि में एक परिशोधन समय होता है|''परिशोधन'' समय <math>O(1)</math> (अर्थात् स्थिरांक) प्रति प्रविष्टि।<ref name="clrs" /><ref name="brown" />
+हीप में एक नए एलिमेंट को डालने का काम सीधे एक नया हीप बनाकर किया जा सकता है जिसमें केवल यह एलिमेंट हो, और फिर उसे मूल हीप से मर्ज करने से होता है। मर्ज के कारण, एकल इंजेक्शन का समय <math>O(\log n)</math> होता है। हालांकि, इसे एक मर्ज प्रक्रिया का उपयोग करके तेज़ किया जा सकता है जो मर्ज के एक बिंदु तक पहुंचते ही मर्ज को शॉर्टकट करता है जहां मर्ज होने वाले दोनों हीप्स में से केवल एक में अधिक ऑर्डर के ट्री हैं। इस स्पीडअप के साथ, लगातार <math>k</math> प्रविष्टियों की एक श्रृंखला में, प्रविष्टियों के लिए कुल समय <math>O(k+\log n)</math> है। इसे बताने का एक और तरीका यह है कि (किसी क्रम में पहली इंसर्शन के लिए लघुगणकीय ओवरहेड के बाद) प्रत्येक क्रमिक '''इन्सर्ट''' में प्रति इंसर्शन <math>O(1)</math> (अर्थात स्थिरांक) का परिशोधन समय होता है।<ref name="clrs" /><ref name="brown" />
-द्विपद ढेर का एक प्रकार, [[तिरछा द्विपद ढेर]], वनों का उपयोग करके निरंतर सबसे खराब स्थिति सम्मिलन समय प्राप्त करता है जिनके पेड़ का आकार द्विआधारी संख्या प्रणाली के बजाय तिरछी द्विआधारी संख्या प्रणाली पर आधारित होता है।<ref>{{citation
+बाइनोमियल हीप का विशेषक रूप, [[तिरछा द्विपद ढेर|स्क्यू बाइनोमियल हीप]], स्क्यू बाइनरी संख्या प्रणाली पर आधारित ट्रीज का उपयोग करके निरंतर खराब गिनती वाला इंजेक्शन समय प्राप्त करता है।<ref>{{citation
   | last1 = Brodal | first1 = Gerth Stølting
   | last2 = Okasaki | first2 = Chris
@@ Line 73: / Line 63: @@
   | volume = 6| doi-access = free
   }}</ref>
+=== फाइंड मिनिमम ===
+हीप के '''मिनिमम''' एलिमेंट को खोजने के लिए, बाइनोमियल ट्रीज की रूट में से मिनिमम एलिमेंट को खोजें। इसे <math>O(\log n)</math> समय में किया जा सकता है, क्योंकि केवल <math>O(\log n)</math> ट्री रूट हैं जिन्हें जांचा जा सकता है।<ref name="clrs" />
+मिनिमम एलिमेंट वाले बायनोमिअल ट्री के लिए एक सूचक का उपयोग करके, इस ऑपरेशन के लिए समय को <math>O(1)</math> तक कम किया जा सकता है। मिनिमम फाइंड के अलावा किसी भी ऑपरेशन को निष्पादित करते समय सूचक को अद्यतन किया जाना चाहिए। यह किसी भी ऑपरेशन के समग्र एसिम्प्टोटिक रनिंग समय को बढ़ाए बिना, प्रति अपडेट <math>O(\log n)</math> बार में किया जा सकता है।
-=== न्यूनतम ज्ञात कीजिए ===
+=== डिलीट मिनिमम ===
-ढेर का न्यूनतम तत्व ज्ञात करने के लिए, द्विपद वृक्षों की जड़ों में से न्यूनतम तत्व ज्ञात करें। इसमें किया जा सकता है <math>O(\log n)</math> समय, जैसा कि अभी है <math>O(\log n)</math> जांचने के लिए पेड़ की जड़ें।<ref name="clrs" />
+हीप से '''मिनिमम एलिमेंट को डिलीट''' करने के लिए, सबसे पहले इस एलिमेंट को खोजें, इसे इसके बाइनोमियल ट्री के रूट से हटा दें, और इसके बच्चों के सबट्रीज की एक सूची प्राप्त करें (जो प्रत्येक अलग-अलग ऑर्डर  के बाइनोमियल ट्री होते हैं)। इन सबट्रीज की सूची को छोटे से बड़े ऑर्डर तक पुनर्व्यवस्थित करके एक अलग बाइनोमियल हीप में परिवर्तित करें। फिर इस हीप को मूल हीप के साथ मर्ज करें। क्योंकि प्रत्येक रूट में अधिकतम <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)
-न्यूनतम तत्व वाले द्विपद वृक्ष के लिए एक सूचक का उपयोग करके, इस ऑपरेशन के समय को कम किया जा सकता है <math>O(1)</math>. न्यूनतम खोजने के अलावा कोई भी ऑपरेशन करते समय पॉइंटर को अपडेट किया जाना चाहिए। इसमें किया जा सकता है <math>O(\log n)</math> प्रति अद्यतन समय, किसी भी ऑपरेशन के समग्र एसिम्प्टोटिक रनिंग समय को बढ़ाए बिना।{{cn|date=October 2019}}
+      min = heap.trees().first()
+      '''for each''' current '''in''' heap.trees()
-=== न्यूनतम हटाएं ===
+          '''if''' current.root < min.root '''then''' min = current
-ढेर से न्यूनतम तत्व को हटाने के लिए, पहले इस तत्व को ढूंढें, इसे इसके द्विपद वृक्ष की जड़ से हटा दें, और इसके उप-वृक्षों की एक सूची प्राप्त करें (जो प्रत्येक स्वयं अलग-अलग क्रम के द्विपद वृक्ष हैं)। उपवृक्षों की इस सूची को सबसे छोटे से सबसे बड़े क्रम में पुन: व्यवस्थित करके एक अलग द्विपद ढेर में बदलें। फिर इस ढेर को मूल ढेर के साथ मिला दें। चूँकि प्रत्येक जड़ में अधिकतम होता है <math>\log_2 n</math> बच्चों, इस नए ढेर को बनाने में समय लगता है <math>O(\log n)</math>. ढेरों को मिलाने में समय लगता है <math>O(\log n)</math>, इसलिए संपूर्ण डिलीट न्यूनतम ऑपरेशन में समय लगता है <math>O(\log n)</math>.<ref name="clrs" />
+      '''for each''' tree '''in''' min.subTrees()
+          tmp.addTree(tree)
-फ़ंक्शन डिलीटमिन (ढेर)
+      heap.removeTree(min)
-      मिनट = ढेर.पेड़().पहला()
+      merge(heap, tmp)
-      heap.trees() में प्रत्येक धारा के लिए
-          यदि current.root < min.root तो min = current
-      min.subTrees() में प्रत्येक पेड़ के लिए
-          tmp.addTree(वृक्ष)
-      ढेर.निकालेंपेड़(मिनट)
-      मर्ज (ढेर, टीएमपी)
-=== कुंजी घटाएं ===
-किसी तत्व की कुंजी कम करने के बाद, यह न्यूनतम-ढेर संपत्ति का उल्लंघन करते हुए, अपने मूल की कुंजी से छोटा हो सकता है। यदि यह मामला है, तो तत्व को उसके माता-पिता के साथ बदलें, और संभवतः उसके दादा-दादी के साथ भी, और इसी तरह, जब तक कि न्यूनतम-ढेर संपत्ति का उल्लंघन न हो जाए। प्रत्येक द्विपद वृक्ष की ऊँचाई अधिकतम होती है <math>\log_2 n</math>, तो यह लेता है <math>O(\log n)</math> समय।<ref name="clrs" />हालाँकि, इस ऑपरेशन के लिए आवश्यक है कि पेड़ के प्रतिनिधित्व में पेड़ में प्रत्येक नोड से उसके मूल तक के पॉइंटर्स शामिल हों, जो अन्य ऑपरेशनों के कार्यान्वयन को कुछ हद तक जटिल बनाता है।<ref name="brown" />
-=== हटाएं ===
-ढेर से किसी तत्व को हटाने के लिए, इसकी कुंजी को नकारात्मक अनंत तक कम करें (या समकक्ष, ढेर में किसी भी तत्व से कुछ कम मूल्य तक) और फिर ढेर में न्यूनतम हटा दें।<ref name="clrs" />
+=== डिक्रीज कुंजी ===
+एक एलिमेंट की कुंजी को कम करने के बाद, यह अपने पैरेंट की कुंजी से छोटा हो सकता है, जिससे मिनिमम-हीप गुणवत्ता को उल्लंघन किया जाता है। यदि ऐसा है, तो एलिमेंट को अपने पैरेंट के साथ विनिमय करें, और शायद इसके साथ ही उसके ग्रैंडपेरेंट और आगे भी, जब तक मिनिमम-हीप गुणवत्ता का उल्लंघन नहीं होता है। प्रत्येक बाइनोमियल ट्री की ऊंचाई अधिकतम <math>\log_2 n</math> होती है, इसलिए इसके लिए <math>O(\log n)</math> समय लगता है।<ref name="clrs" /> हालांकि, यह ऑपरेशन यह भी आवश्यक करता है कि ट्री का प्रतिनिधि उसके पैरेंट से पॉइंटर्स को इन्सर्ट, जिससे अन्य ऑपरेशनों के अंगीकरण को कुछ प्रकार से जटिल किया जाता है।<ref name="brown" />
+=== डिलीट ===
+हीप से एक एलिमेंट को '''डिलीट''' करने के लिए, इसकी कुंजी को नकारात्मक अविन्फिनिटी (या समतुल्य रूप से, हीप में किसी भी एलिमेंट से कम मान) करें और फिर हीप में मिनिमम एलिमेंट को हटा दें।<ref name="clrs" />
 == अनुप्रयोग ==
-* [[असतत घटना अनुकरण]]
+*[[असतत घटना अनुकरण|डिस्क्रीट इवेंट सिमुलेशन]]
-* प्राथमिकता कतारें
+* प्रायोरिटी क्यू
 == यह भी देखें ==
-* [[कमजोर ढेर]], द्विआधारी ढेर और द्विपद ढेर डेटा संरचनाओं का एक संयोजन
+* [[कमजोर ढेर|वीक हीप]], बाइनरी हीप और बाइनोमियल हीप डेटा स्ट्रक्चरओं का एक संयोजन है।
 == संदर्भ ==
@@ Line 112: / Line 95: @@
 == बाहरी संबंध ==
-* [http://www.cs.unc.edu/~bbb/#binomial_heaps Two C implementations of binomial heap] (a generic one and one optimized for integer keys)
+* [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]
 * [https://github.com/vy/binomial-heap Common Lisp implementation of binomial heap]
 {{Data structures}}
-[[Category: ढेर (डेटा संरचनाएं)]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:Collapse templates]]
 [[Category:Created On 10/07/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Missing redirects]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with script errors]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:ढेर (डेटा संरचनाएं)]]

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

Latest revision as of 12:35, 28 July 2023

Contents

बायनोमिअल हीप

बायनोमिअल हीप की संरचना

कार्यान्वयन

मर्ज

इन्सर्ट

फाइंड मिनिमम

डिलीट मिनिमम

डिक्रीज कुंजी

डिलीट

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 12:35, 28 July 2023

बायनोमिअल हीप

बायनोमिअल हीप की संरचना

कार्यान्वयन

मर्ज

इन्सर्ट

फाइंड मिनिमम

डिलीट मिनिमम

डिक्रीज कुंजी

डिलीट

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories