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

Revision as of 17:46, 25 July 2023

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

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

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

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

Error creating thumbnail:

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

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

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

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

हीप में प्रत्येक बायनोमिअल ट्री न्यूनतम-हीप गुणधर्म का पालन करता है: एक नोड की key उसके मूल की key से बड़ी या उसके बराबर होती है।
प्रत्येक ऑर्डर के लिए, शून्य ऑर्डर सहित, अधिकतम एक बायनोमिअल ट्री हो सकता है।

प्रथम गुणधर्म यह सुनिश्चित करती है कि प्रत्येक बायनोमिअल ट्री की रूट में ट्री की सबसे छोटी key सम्मिलित है। इसका अर्थ यह है कि पूरे हीप में सबसे छोटी key रूट्स में से एक है।^[1]

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

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

अंगूठे ऑर्डर वाले तीन बायनोमिअल ट्री हैं

विभिन्न keys वाली $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

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

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

   function mergeTree(p, q)   
      if p.root.key <= q.root.key
          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)$ बार में किया जा सकता है।^{[citation needed]}

डिलीट मिनिमम

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

डिक्रीज key

एक एलिमेंट की key को कम करने के बाद, यह अपने पैरेंट की key से छोटा हो सकता है, जिससे न्यूनतम-हीप गुणवत्ता को उल्लंघन किया जाता है। यदि ऐसा है, तो एलिमेंट को अपने पैरेंट के साथ विनिमय करें, और शायद इसके साथ ही उसके ग्रैंडपेरेंट और आगे भी, जब तक न्यूनतम-हीप गुणवत्ता का उल्लंघन नहीं होता है। प्रत्येक बाइनोमियल ट्री की ऊंचाई अधिकतम $\log _{2}n$ होती है, इसलिए इसके लिए $O(\log n)$ समय लगता है।^[1] हालांकि, यह ऑपरेशन यह भी आवश्यक करता है कि ट्री का प्रतिनिधि उसके पैरेंट से पॉइंटर्स को इन्सर्ट, जिससे अन्य ऑपरेशनों के अंगीकरण को कुछ प्रकार से जटिल किया जाता है।^[3]

डिलीट

हीप से एक एलिमेंट को डिलीट करने के लिए, इसकी key को नकारात्मक अविन्फिनिटी (या समतुल्य रूप से, हीप में किसी भी एलिमेंट से कम मान) करें और फिर हीप में न्यूनतम एलिमेंट को हटा दें।^[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: @@
-{{redirect|Binomial tree|binomial price trees|binomial options pricing model}}
+{{redirect|बायनोमिअल ट्री|बायनोमिअल प्राइस ट्री|बायनोमिअल ऑप्शन प्राइसिंग मॉडल}}
-[[कंप्यूटर विज्ञान]] में, एक बिनोमियल हीप एक [[डेटा संरचना]] है जो [[प्राथमिकता कतार]] के रूप में कार्य करती है लेकिन साथ ही [[पिघलने योग्य ढेर|बिनोमियल हीपों]] के जोड़े जा सकते हैं। यह मर्ज़ किए जा सकने वाले हीप [[अमूर्त डेटा प्रकार|अभिसारण डेटा प्रकार]] (जिसे [[विलय योग्य ढेर]] भी कहा जाता है) के रूप में एक अमूल्य संरचना है, जिसमें मर्ज़ के ऑपरेशन का समर्थन किया जाता है। यह एक हीप के रूप में प्रदर्शित होता है, जो एक [[ बाइनरी ढेर |बाइनरी हीप]] के समान होता है, लेकिन इसमें विशेष तरह का वृक्ष संरचना उपयोग किया जाता है जो बाइनरी हीप्स द्वारा उपयोग किए जाने वाले पूर्ण बाइनरी वृक्षों से भिन्न होता है।<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" />
+एक बायनोमिअल हीप को बायनोमिअल [[वृक्ष डेटा संरचना|ट्रीज]] के एक सेट के रूप में कार्यान्वित किया जाता है (बाइनरी हीप के साथ तुलना करें, जिसमें एकल [[द्विआधारी वृक्ष|बाइनरी ट्री]] का आकार होता है), जिन्हें निम्नानुसार पुनरावर्ती रूप से परिभाषित किया गया है:<ref name="clrs" />
-* ऑर्डर 0 का एक द्विपद वृक्ष एक एकल नोड है
+* ऑर्डर 0 का एक बायनोमिअल ट्री एकल नोड होता है
-* क्रम <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 क्रम के द्विपद वृक्ष: प्रत्येक वृक्ष में सभी निचले क्रम वाले द्विपद वृक्षों के उपवृक्षों के साथ एक जड़ नोड होता है, जिसे हाइलाइट किया गया है। उदाहरण के लिए, क्रम 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>
+[[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" />
-* ढेर में प्रत्येक द्विपद वृक्ष [[न्यूनतम-ढेर संपत्ति]] का पालन करता है: एक नोड की कुंजी उसके मूल की कुंजी से बड़ी या उसके बराबर होती है।
+* हीप में प्रत्येक बायनोमिअल ट्री [[न्यूनतम-ढेर संपत्ति|न्यूनतम-हीप गुणधर्म]] का पालन करता है: एक नोड की key उसके मूल की key से बड़ी या उसके बराबर होती है।
-* प्रत्येक क्रम के लिए, शून्य क्रम सहित, अधिकतम एक द्विपद वृक्ष हो सकता है।
+* प्रत्येक ऑर्डर के लिए, शून्य ऑर्डर सहित, अधिकतम एक बायनोमिअल ट्री हो सकता है।
-पहली संपत्ति यह सुनिश्चित करती है कि प्रत्येक द्विपद वृक्ष की जड़ में वृक्ष की सबसे छोटी कुंजी शामिल है। इसका मतलब यह है कि पूरे ढेर में सबसे छोटी कुंजी जड़ों में से एक है।<ref name="clrs" />
+प्रथम गुणधर्म यह सुनिश्चित करती है कि प्रत्येक बायनोमिअल ट्री की रूट में ट्री की सबसे छोटी key सम्मिलित है। इसका अर्थ यह है कि पूरे हीप में सबसे छोटी key रूट्स में से एक है।<ref name="clrs" />
-एक द्विपद ढेर को द्विपद पेड़ों के एक सेट के रूप में कार्यान्वित किया जाता है जो द्विपद ढेर गुणों को संतुष्ट करते हैं:* ढेर में प्रत्येक द्विपद वृक्ष  का पालन करता है: एक नोड की कुंजी उसके मूल की कुंजी से बड़ी या उसके बराबर होती है।
+किसी बायनोमिअल हीप को बायनोमिअल ट्रीज के एक सेट के रूप में कार्यान्वित किया जाता है जो बायनोमिअल हीप गुणों को संतुष्ट करते हैं:* हीप में प्रत्येक बायनोमिअल ट्री  का पालन करता है: एक नोड की key उसके मूल की key से बड़ी या उसके बराबर होती है।
-दूसरी संपत्ति का तात्पर्य है कि <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|अंगूठे ऑर्डर वाले तीन बायनोमिअल ट्री हैं]]विभिन्न keys वाली <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>11 वस्तुओं को एक द्विपद ढेर में व्यवस्थित करने के विभिन्न तरीकों की संख्या <math>n!</math> के सबसे बड़े विषम भाजक के बराबर होती है। 33 के लिए ये संख्याएँ हैं
+यदि 11 वस्तुओं को समान रूप से यादृच्छिक ऑर्डर में बायनोमिअल हीप में डाला जाता है, तो इनमें से प्रत्येक व्यवस्था समान रूप से संभावित है।<ref name="brown" />
-, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, ... {{OEIS|A049606}}
-यदि 11 वस्तुओं को समान रूप से यादृच्छिक क्रम में द्विपद ढेर में डाला जाता है, तो इनमें से प्रत्येक व्यवस्था समान रूप से संभावित है।<ref name="brown" />
-== कार्यान्वयन ==
 == कार्यान्वयन ==
+क्योंकि किसी भी ऑपरेशन के लिए बायनोमिअल ट्रीज के मूल नोड्स तक यादृच्छिक पहुंच की आवश्यकता नहीं होती है, बायनोमिअल ट्रीज की रूट्स को ट्री के बढ़ते ऑर्डर के अनुसार एक लिंक की गई सूची में संग्रहीत किया जा सकता है। चूँकि प्रत्येक नोड के लिए बच्चों की संख्या परिवर्तनशील है, इसलिए प्रत्येक नोड के लिए अपने प्रत्येक चाइल्ड के लिए अलग-अलग लिंक रखना अच्छी तरह से काम नहीं करता है, जैसा कि एक बाइनरी ट्री में आम होगा; इसके बजाय, प्रत्येक नोड से ट्री में उसके उच्चतम-ऑर्डर वाले चाइल्ड और उससे अगले छोटे ऑर्डर के उसके भाई-बहन के लिंक का उपयोग करके इस ट्री को लागू करना संभव है। इन सिबलिंग पॉइंटर्स को प्रत्येक नोड के बच्चों की लिंक की गई सूची में अगले पॉइंटर्स के रूप में व्याख्या किया जा सकता है, लेकिन रूट्स की लिंक की गई सूची से विपरीत ऑर्डर के साथ: सबसे बड़े से सबसे छोटे ऑर्डर के बजाय, इसके विपरीत। यह प्रतिनिधित्व एक ही ऑर्डर के दो ट्रीज को एक साथ जोड़ने की अनुमति देता है, जिससे निरंतर समय में अगले बड़े ऑर्डर का ट्री बनता है।
-क्योंकि किसी भी ऑपरेशन के लिए द्विपद वृक्षों के मूल नोड्स तक यादृच्छिक पहुंच की आवश्यकता नहीं होती है, द्विपद वृक्षों की जड़ों को वृक्ष के बढ़ते क्रम के अनुसार एक लिंक की गई सूची में संग्रहीत किया जा सकता है। चूँकि प्रत्येक नोड के लिए बच्चों की संख्या परिवर्तनशील है, इसलिए प्रत्येक नोड के लिए अपने प्रत्येक बच्चे के लिए अलग-अलग लिंक रखना अच्छी तरह से काम नहीं करता है, जैसा कि एक बाइनरी ट्री में आम होगा; इसके बजाय, प्रत्येक नोड से पेड़ में उसके उच्चतम-क्रम वाले बच्चे और उससे अगले छोटे क्रम के उसके भाई-बहन के लिंक का उपयोग करके इस पेड़ को लागू करना संभव है। इन सिबलिंग पॉइंटर्स को प्रत्येक नोड के बच्चों की लिंक की गई सूची में अगले पॉइंटर्स के रूप में व्याख्या किया जा सकता है, लेकिन जड़ों की लिंक की गई सूची से विपरीत क्रम के साथ: सबसे बड़े से सबसे छोटे क्रम के बजाय, इसके विपरीत। यह प्रतिनिधित्व एक ही क्रम के दो पेड़ों को एक साथ जोड़ने की अनुमति देता है, जिससे निरंतर समय में अगले बड़े क्रम का पेड़ बनता है।
 === मर्ज ===
-[[File:Binomial heap merge1.svg|thumb|200px|एक ही क्रम के दो द्विपद वृक्षों को मर्ज करने के लिए, पहले रूट कुंजी की तुलना करें। 7>3 के बाद से, बाईं ओर का काला पेड़ (रूट नोड 7 के साथ) दाईं ओर के भूरे पेड़ से (रूट नोड 3 के साथ) एक उपवृक्ष के रूप में जुड़ा हुआ है। परिणाम क्रम 3 का एक पेड़ है।]]दो ढेरों को मर्ज करने के ऑपरेशन का उपयोग अधिकांश अन्य ऑपरेशनों में सबरूटीन के रूप में किया जाता है।
+[[File:Binomial heap merge1.svg|thumb|200px|एक ही ऑर्डर के दो बायनोमिअल ट्रीज को मर्ज करने के लिए, पहले रूट key की तुलना करें। 7>3 के बाद से, बाईं ओर का काला ट्री (रूट नोड 7 के साथ) दाईं ओर के भूरे ट्री से (रूट नोड 3 के साथ) एक उपट्री के रूप में जुड़ा हुआ है। परिणाम ऑर्डर 3 का एक ट्री है।]]दो हीप्स को मर्ज करने की ऑपरेशन को अधिकांश अन्य ऑपरेशनों में एक सबरूटीन के रूप में उपयोग किया जाता है। इस प्रक्रिया के भीतर एक मूल सबरूटीन, एक ही ऑर्डर के बाइनोमियल ट्री के जोड़ा बनाने के लिए उपयोग किया जाता है। इसे दो ट्री के रूट्स पर मौजूद keys की तुलना करके किया जा सकता है (दोनों ट्री में सबसे छोटी keys)। बड़े key वाले रूट नोड को छोटे key वाले रूट नोड का एक चाइल्ड बनाया जाता है, जिससे उसका ऑर्डर एक के साथ बढ़ जाता है:<ref name="clrs" /><ref name="brown" />
-इस प्रक्रिया के अंतर्गत एक बुनियादी सबरूटीन एक ही क्रम के द्विपद वृक्षों के जोड़े को मिलाता है। यह दो पेड़ों की जड़ों की कुंजियों (दोनों पेड़ों की सबसे छोटी कुंजियाँ) की तुलना करके किया जा सकता है। बड़ी कुंजी वाले रूट नोड को छोटी कुंजी वाले रूट नोड के चाइल्ड में बनाया जाता है, जिससे उसका क्रम एक बढ़ जाता है:<ref name="clrs" /><ref name="brown" />
+    '''function''' mergeTree(p, q)
+       '''if''' p.root.key <= q.root.key
-फ़ंक्शन मर्जट्री (पी, क्यू);
+           '''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 77: / Line 64: @@
   | 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> बार में किया जा सकता है।{{cn|date=October 2019}}
-=== न्यूनतम ज्ञात कीजिए ===
+=== डिलीट मिनिमम ===
-ढेर का न्यूनतम तत्व ज्ञात करने के लिए, द्विपद वृक्षों की जड़ों में से न्यूनतम तत्व ज्ञात करें। इसमें किया जा सकता है <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" />
+=== डिक्रीज key ===
+एक एलिमेंट की key को कम करने के बाद, यह अपने पैरेंट की key से छोटा हो सकता है, जिससे न्यूनतम-हीप गुणवत्ता को उल्लंघन किया जाता है। यदि ऐसा है, तो एलिमेंट को अपने पैरेंट के साथ विनिमय करें, और शायद इसके साथ ही उसके ग्रैंडपेरेंट और आगे भी, जब तक न्यूनतम-हीप गुणवत्ता का उल्लंघन नहीं होता है। प्रत्येक बाइनोमियल ट्री की ऊंचाई अधिकतम <math>\log_2 n</math> होती है, इसलिए इसके लिए <math>O(\log n)</math> समय लगता है।<ref name="clrs" /> हालांकि, यह ऑपरेशन यह भी आवश्यक करता है कि ट्री का प्रतिनिधि उसके पैरेंट से पॉइंटर्स को इन्सर्ट, जिससे अन्य ऑपरेशनों के अंगीकरण को कुछ प्रकार से जटिल किया जाता है।<ref name="brown" />
+=== डिलीट ===
+हीप से एक एलिमेंट को डिलीट करने के लिए, इसकी key को नकारात्मक अविन्फिनिटी (या समतुल्य रूप से, हीप में किसी भी एलिमेंट से कम मान) करें और फिर हीप में न्यूनतम एलिमेंट को हटा दें।<ref name="clrs" />
 == अनुप्रयोग ==
-* [[असतत घटना अनुकरण]]
+*[[असतत घटना अनुकरण|डिस्क्रीट इवेंट सिमुलेशन]]
-* प्राथमिकता कतारें
+* प्रायोरिटी क्यू
 == यह भी देखें ==
-* [[कमजोर ढेर]], द्विआधारी ढेर और द्विपद ढेर डेटा संरचनाओं का एक संयोजन
+* [[कमजोर ढेर|वीक हीप]], बाइनरी हीप और बाइनोमियल हीप डेटा स्ट्रक्चरओं का एक संयोजन है।
 == संदर्भ ==

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 17:46, 25 July 2023

Contents

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

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

कार्यान्वयन

मर्ज

इन्सर्ट

फाइंड मिनिमम

डिलीट मिनिमम

डिक्रीज key

डिलीट

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 17:46, 25 July 2023

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

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

कार्यान्वयन

मर्ज

इन्सर्ट

फाइंड मिनिमम

डिलीट मिनिमम

डिक्रीज key

डिलीट

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories