सी ++ में द्विपद ढेर?

द्विपद हीप को बाइनरी हीप के विस्तार के रूप में परिभाषित किया गया है जो बाइनरी हीप द्वारा प्रदान किए गए अन्य कार्यों के साथ तेजी से विलय या संघ संचालन प्रदान करता है।

द्विपद ढेर को द्विपद वृक्षों के संग्रह के रूप में माना जाता है।

द्विपद वृक्ष क्या है?

क्रम k-1 के दो द्विपद वृक्षों को लेकर और एक को सबसे बाएं बच्चे या दूसरे के रूप में मानकर k क्रम का एक द्विपद वृक्ष बनाया जा सकता है।

क्रम k के द्विपद वृक्ष में निम्न गुण होते हैं।

• द्विपद वृक्ष के नोड्स की संख्या ठीक 2 ^k . है ।

• द्विपद वृक्ष की गहराई k है।

• गहराई पर बिल्कुल kCi नोड हैं जहाँ i =0, 1, . . . , के.

• डिग्री k वाली जड़ और जड़ के बच्चों को स्वयं द्विपद वृक्ष माना जाता है, क्रम k-1, k-2,..0 बाएं से दाएं।

द्विपद ढेर -

एक द्विपद ढेर को द्विपद वृक्षों के एक समूह के रूप में परिभाषित किया गया है जहां प्रत्येक द्विपद वृक्ष MinHeap संपत्ति का अनुसरण करता है। और किसी भी डिग्री के होने पर किसी भी डिग्री का अधिकतम एक द्विपद वृक्ष हो सकता है।

उदाहरण द्विपद हीप -

एक द्विपद ढेर जिसमें 12 नोड होते हैं। इसे 2 के संग्रह के रूप में माना जाता है

क्रम 2 और 3 के बाएँ से दाएँ द्विपद वृक्ष

द्विपद ढेर और एक संख्या का द्विआधारी प्रतिनिधित्व

एक द्विपद हीप जिसमें m नोड होते हैं, में द्विपद वृक्षों की संख्या m के बाइनरी प्रतिनिधित्व में सेट बिट्स की संख्या के बराबर होती है। उदाहरण के लिए, मान लीजिए कि एम 13 है, एम (00001101) के द्विआधारी प्रतिनिधित्व में 3 सेट बिट्स हैं, जो 3 द्विपद वृक्षों को दर्शाता है। हम इन द्विपद वृक्षों की डिग्री को सेट बिट्स की स्थिति के साथ जोड़ने में सक्षम हो सकते हैं। इस संबंध की सहायता से, हम यह निर्णय या निष्कर्ष निकाल सकते हैं कि 'm' नोड्स वाले द्विपद ढेर में O(logm) द्विपद वृक्ष हैं

द्विपद हीप के संचालन -

यूनियन () द्विपद हीप में मुख्य ऑपरेशन है, अन्य सभी ऑपरेशन मुख्य रूप से इस ऑपरेशन को लागू करते हैं। संघ () ऑपरेशन दो द्विपद ढेर को एक में मिलाने के लिए जिम्मेदार है।

• इन्सर्ट (एच, के) - द्विपद हीप 'एच' में एक कुंजी 'के' डालें। सबसे पहले, यह ऑपरेशन एकल कुंजी 'के' के साथ एक द्विपद हीप बनाने में सक्षम है, फिर एच और नए द्विपद ढेर पर संघ को कॉल करता है।

• getMin(h)− मिन () प्राप्त करने की एक सरल विधि द्विपद वृक्ष की जड़ की सूची पर जाना और सबसे छोटी कुंजी को वापस करना है।

  इस एप्लिकेशन को O(logm) समय की आवश्यकता है। पॉइंटर को सबसे छोटी कुंजी रूट बनाए रखकर इसे O(1) में सुधारा जा सकता है।

• ExtractMin(h)− यह ऑपरेशन यूनियन () को भी लागू करता है। सबसे पहले, हम सबसे छोटी कुंजी बिनोमियल ट्री की गणना करने के लिए getMin() को कॉल करते हैं, इसके बाद हम नोड को हटाते हैं और हटाए गए सबसे छोटे नोड के सभी सबट्री को मिलाकर एक नया द्विपद हीप बनाते हैं। अंत में, हम h और साथ ही नव निर्मित द्विपद हीप पर कॉलुनियन () कहते हैं। इस ऑपरेशन के लिए O(logm) समय की आवश्यकता है।

• हटाएं (एच) - बाइनरी हीप के समान, सबसे पहले, डिलीट ऑपरेशन कुंजी को घटाकर माइनसइनफिनिट, अगली कॉल एक्सट्रैक्टमिन () को कम कर देता है।

• कमीके (एच) - कमीके () भी बाइनरी हीप के समान है। सबसे पहले, हम माता-पिता के साथ घटती कुंजी की तुलना करते हैं और यदि माता-पिता की कुंजी अधिक है, तो हम कुंजी का आदान-प्रदान करते हैं और माता-पिता की पुनरावृत्ति करते हैं। अंत में, हम रुक जाते हैं जब हम या तो एक नोड तक पहुँचते हैं जिसके माता-पिता की एक छोटी कुंजी होती है या हम रूट नोड पर पहुँचते हैं। कमी की समय जटिलताकी() हे (लॉगम) है।