द्विपद हीप

"बायनोमिअल ट्री" redirects here. For बायनोमिअल प्राइस ट्री, see बायनोमिअल ऑप्शन प्राइसिंग मॉडल.

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

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

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

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

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

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

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

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

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

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

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

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

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

कार्यान्वयन

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

मर्ज

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

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

   function mergeTree(p, q)   
      if p.root.key <= q.root.key
          return p.addSubTree(q)
      else
          return q.addSubTree(p)

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

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

 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()

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

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

  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)$ समय लगता है। हालांकि, यह ऑपरेशन यह भी आवश्यक करता है कि ट्री का प्रतिनिधि उसके पैरेंट से पॉइंटर्स को इन्सर्ट, जिससे अन्य ऑपरेशनों के अंगीकरण को कुछ प्रकार से जटिल किया जाता है।

डिलीट

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

अनुप्रयोग

• डिस्क्रीट इवेंट सिमुलेशन
• प्रायोरिटी क्यू

यह भी देखें

• वीक हीप, बाइनरी हीप और बाइनोमियल हीप डेटा स्ट्रक्चरओं का एक संयोजन है।

बाहरी संबंध

• 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