बाइनोमियल हीप को बाइनरी हीप के विस्तार के रूप में परिभाषित किया गया है जो बाइनरी हीप द्वारा प्रदान किए गए अन्य ऑपरेशन्स के साथ तेज़ मर्ज या यूनियन ऑपरेशन प्रदान करता है।
एक बाइनोमियल हीप को बाइनोमियल ट्रीज़ के संग्रह के रूप में माना जाता है।
बाइनोमियल ट्री क्या है?
k क्रम का एक बाइनोमियल ट्री k-1 क्रम के दो बाइनोमियल ट्रीज़ लेकर और एक को बाएं बच्चे या दूसरे के रूप में मानकर बनाया जा सकता है।
k क्रम के बाइनोमियल ट्री में नीचे दिए गए गुण होते हैं।
बाइनोमियल ट्री के नोड्स की संख्या ठीक 2k होती है।
बाइनोमियल ट्री की गहराई k होती है।
गहराई i पर ठीक kCi नोड्स होते हैं जहां i = 0, 1, ..., k।
k डिग्री का रूट और रूट के बच्चे स्वयं k-1, k-2,..0 क्रम के बाइनोमियल ट्रीज़ के रूप में माने जाते हैं बाएं से दाएं।
बाइनोमियल हीप -
एक बाइनोमियल हीप को बाइनोमियल ट्रीज़ के सेट के रूप में परिभाषित किया गया है जहां प्रत्येक बाइनोमियल ट्री मिन हीप गुण का पालन करता है। और किसी भी डिग्री होने पर, किसी भी डिग्री का अधिकतम एक बाइनोमियल ट्री हो सकता है।
उदाहरण बाइनोमियल हीप -

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

बाइनोमियल हीप्स और एक संख्या का बाइनरी प्रतिनिधित्व
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) है।