Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में बाइनोमियल हीप


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

एक बाइनोमियल हीप को बाइनोमियल ट्रीज़ के संग्रह के रूप में माना जाता है।

बाइनोमियल ट्री क्या है?

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

k क्रम के बाइनोमियल ट्री में नीचे दिए गए गुण होते हैं।

  • बाइनोमियल ट्री के नोड्स की संख्या ठीक 2k होती है।

  • बाइनोमियल ट्री की गहराई k होती है।

  • गहराई i पर ठीक kCi नोड्स होते हैं जहां i = 0, 1, ..., k।

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

बाइनोमियल हीप -

एक बाइनोमियल हीप को बाइनोमियल ट्रीज़ के सेट के रूप में परिभाषित किया गया है जहां प्रत्येक बाइनोमियल ट्री मिन हीप गुण का पालन करता है। और किसी भी डिग्री होने पर, किसी भी डिग्री का अधिकतम एक बाइनोमियल ट्री हो सकता है।

उदाहरण बाइनोमियल हीप -

C++ में बाइनोमियल हीप


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

बाएं से दाएं 2 और 3 क्रम के बाइनोमियल ट्रीज़

C++ में बाइनोमियल हीप


बाइनोमियल हीप्स और एक संख्या का बाइनरी प्रतिनिधित्व

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

बाइनोमियल हीप के ऑपरेशन्स -

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

  • insert(h, K) - कुंजी 'K' को बाइनोमियल हीप 'h' में सम्मिलित करता है। सबसे पहले, यह ऑपरेशन एकल कुंजी 'K' के साथ एक बाइनोमियल हीप बनाने में सक्षम है, फिर h और नए बाइनोमियल हीप पर यूनियन कॉल करता है।

  • getMin(h) - getMin() का एक सरल तरीका बाइनोमियल ट्रीज़ के रूट की सूची पर जाना और सबसे छोटी कुंजी लौटाना है।

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

  • extractMin(h) - यह ऑपरेशन भी union() को लागू करता है। सबसे पहले, हम सबसे छोटी कुंजी बाइनोमियल ट्री की गणना के लिए getMin() कॉल करते हैं, अगला हम नोड को हटाते हैं और हटाए गए सबसे छोटे नोड के सभी सबट्रीज़ को संयोजित करके एक नया बाइनोमियल हीप बनाते हैं। अंत में, हम h के साथ-साथ नए बने बाइनोमियल हीप पर union() कॉल करते हैं। इस ऑपरेशन के लिए O(log m) समय लगता है।

  • delete(h) - बाइनरी हीप के समान, सबसे पहले, डिलीट ऑपरेशन कुंजी को माइनस इनफिनिट तक कम करता है, फिर extractMin() कॉल करता है।

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


  1. C++ में द्विपद हीप का मेमोरी प्रतिनिधित्व C++ में द्विपद हीप का मेमोरी प्रतिनिधित्व

    द्विपद वृक्ष क्या है? द्विपद वृक्ष एक क्रमबद्ध वृक्ष डेटा संरचना है, मान लीजिए B0 में एक नोड होता है जबकि Bk के रूप में दर्शाया गया द्विपद वृक्ष दो द्विपद वृक्षों यानी Bk-1 से मिलकर होता है जो एक साथ जुड़े होते हैं। एक द्विपद वृक्ष की जड़ दूसरे द्विपद वृक्ष की जड़ का बायां बच्चा होती है। द्विपद वृक्

  1. C++ में जांचें कि दिया गया बाइनरी ट्री हीप है या नहीं C++ में जांचें कि दिया गया बाइनरी ट्री हीप है या नहीं

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

  1. C++ में मैक्स हीप में न्यूनतम एलिमेंट C++ में मैक्स हीप में न्यूनतम एलिमेंट

    समस्या कथनमैक्स हीप में सबसे कम मान वाला एलिमेंट ढूंढें।नीचे दिए गए मैक्स हीप पर विचार करें।मैक्स हीप में रूट नोड का मान हमेशा उसके बच्चों से अधिक होता है। इस गुण के कारण, हम निष्कर्ष निकाल सकते हैं कि मान लीफ नोड्स में से एक में मौजूद होगा। यदि हीप में n नोड्स हैं तो ceil(n/2) लीफ होंगे।मैक्स हीप ए