Fibonacci heap डेटा संरचना में इसके नाम पर "फाइबोनैकी" शब्द है, लेकिन डेटा संरचना में कुछ भी फिबोनाची संख्याओं का उपयोग नहीं करता है। विकिपीडिया लेख के मुताबिक:एक फाइबोनैकी ढेर क्यों एक फाइबोनैकी ढेर कहा जाता है?
फिबोनाची ढेर का नाम फिबोनाची संख्याओं से आता है जो चलने वाले समय विश्लेषण में उपयोग किए जाते हैं।
फिबोनाची ढेर में ये फाइबोनैकी संख्याएं कैसे उत्पन्न होती हैं?
फाइबोनैकी ढेर अलग-अलग "ऑर्डर" के छोटे ढेर-आदेशित पेड़ों के संग्रह से बना है जो कुछ संरचनात्मक बाधाओं का पालन करते हैं। फाइबोनैकी अनुक्रम उत्पन्न होता है क्योंकि इन पेड़ों को इस तरह से बनाया जाता है कि आदेश एन के पेड़ में कम से कम एफ एन + 2 नोड्स हैं, जहां एफ एन + 2 (एन + 2) nd फाइबोनैकी संख्या है।
यह देखने के लिए कि यह परिणाम क्यों सच है, चलो देखते हैं कि फाइबोनैकी ढेर में पेड़ कैसे बनाए जाते हैं। प्रारंभ में, जब भी एक नोड को फिबोनाची ढेर में रखा जाता है, तो उसे ऑर्डर 0 के पेड़ में रखा जाता है जिसमें केवल उस नोड होता है। जब भी फिबोनाची ढेर से एक मूल्य हटा दिया जाता है, तो फिबोनाची ढेर में से कुछ पेड़ों को एक साथ जोड़ दिया जाता है ताकि वृक्षों की संख्या बहुत बड़ी न हो।
पेड़ों को एक साथ जोड़ते समय, फाइबोनैकी ढेर केवल उसी क्रम के पेड़ को जोड़ती है। ऑर्डर एन के दो पेड़ों को क्रमशः एन + 1 के पेड़ में गठबंधन करने के लिए, फाइबोनैकी ढेर जो भी दो पेड़ों में से दूसरे की तुलना में अधिक रूट मान होता है, तब वह पेड़ दूसरे पेड़ का बच्चा बनाता है। इस तथ्य का एक परिणाम यह है कि ऑर्डर के वृक्षों में हमेशा एन बच्चे होते हैं।
फाइबोनैकी ढेर का मुख्य आकर्षण यह है कि यह कुशलतापूर्वक कमी (कुंजी ए (1) में) का समर्थन करता है। इसका समर्थन करने के लिए, फाइबोनैकी ढेर निम्नानुसार कमी-कुंजी लागू करता है: कुछ नोड में संग्रहीत मूल्य की कुंजी को कम करने के लिए, नोड अपने मूल पेड़ से काटा जाता है और अपने स्वयं के अलग पेड़ के रूप में माना जाता है। जब ऐसा होता है, तो उसके पुराने माता-पिता नोड का क्रम एक से कम हो जाता है। उदाहरण के लिए, यदि एक आदेश 4 पेड़ से एक बच्चा इसकाटता है, तो यह एक आदेश 3 पेड़ तक गिर जाता है, जो समझ में आता है क्योंकि पेड़ का क्रम उस बच्चों की संख्या माना जाता है।
ऐसा करने में समस्या यह है कि यदि एक ही पेड़ से बहुत सारे पेड़ काट दिया जाता है, तो हमारे पास एक बड़े आदेश के साथ एक पेड़ हो सकता है लेकिन जिसमें बहुत कम नोड्स होते हैं। फिबोनाची ढेर की समय गारंटी केवल तभी संभव होती है जब बड़े आदेश वाले पेड़ों में बड़ी संख्या में नोड्स होते हैं, और यदि हम किसी भी नोड्स को काट सकते हैं तो हम पेड़ से चाहेंगे, हम आसानी से ऐसी परिस्थिति में आ सकते हैं जहां एक बड़े आदेश वाले पेड़ केवल नोड्स की एक छोटी संख्या होती है।
इसे हल करने के लिए, फिबोनाची ढेर एक आवश्यकता बनाते हैं - यदि आप एक पेड़ से दो बच्चों को काटते हैं, तो आपको उस पेड़ को अपने माता-पिता से बदलना होगा। इसका मतलब है कि एक पेबोनैकी ढेर बनाने वाले पेड़ कम-से-कम होने से बहुत बुरी तरह क्षतिग्रस्त नहीं होंगे।
और अब हम फिबोनाची संख्याओं के बारे में जानकारी प्राप्त कर सकते हैं। इस बिंदु पर, हम फिबोनाची ढेर में पेड़ों के बारे में निम्नलिखित कह सकते हैं:
तो अब हम पूछ सकते हैं - इन धारणाओं के तहत आप सबसे छोटे संभव पेड़ क्या कर सकते हैं?
चलो कुछ उदाहरणों को आज़माएं।
Smallest possible order 0 tree: *
क्रम 1 की छोटी संभव पेड़ एक बच्चे के साथ कम से कम एक नोड होना चाहिए था: वहाँ सिर्फ एक ही क्रम 0 के संभावित पेड़ है, जो एक बस एक ही नोड है।
Smallest possible order 1 tree: *
|
*
क्या आदेश 2 के सबसे छोटे पेड़ के बारे में: छोटी संभव बच्चे हम कर सकता है के साथ जो इस पेड़ है एक बच्चे के रूप में सबसे छोटी क्रम -0 पेड़, एक एकल नोड है? यही हैं जहां बातें दिलचस्प हो जाती हैं। इस पेड़ में निश्चित रूप से दो बच्चे होने चाहिए, और यह आदेश के दो पेड़ों को एक साथ विलय करके गठित किया जाएगा। नतीजतन, पेड़ के शुरू में दो बच्चे होंगे - आदेश का पेड़ 0 और आदेश का पेड़ 1. लेकिन याद रखें - हम कर सकते हैं बच्चों को विलय के बाद पेड़ से दूर करो!
Smallest possible order 2 tree: *
/\
* *
कैसे आदेश 3 के बारे में: इस मामले में, अगर हम आदेश 1 के वृक्ष के बच्चे दूर कटौती, हम एक पेड़ के साथ दो बच्चे हैं, जो दोनों के आदेश 0 के पेड़ हैं के साथ छोड़ दिया जाएगा? पहले की तरह, यह पेड़ दो आदेशों के दो पेड़ों को विलय करके बनाया जाएगा। फिर हम इस आदेश-3 पेड़ जितना संभव हो उतना उपट्री काटने की कोशिश करेंगे। जब यह बनाया जाता है, तो पेड़ के आदेश 2, 1, और 0 के उप-नियम होते हैं। हम 0 पेड़ के आदेश से दूर नहीं जा सकते हैं, लेकिन हम ऑर्डर 2 और ऑर्डर 1 पेड़ से एक ही बच्चे को काट सकते हैं।
Smallest possible order 3 tree: *
/|\
* * *
|
*
अब हम एक पैटर्न देखा जा सकता है: हम ऐसा करते हैं, तो हम तीन बच्चों, आदेश 1 में से एक है, और दो आदेश 2 के साथ एक पेड़ के साथ छोड़ दिया जाता है। सबसे छोटा संभव आदेश- (एन + 2) पेड़ निम्नानुसार बनाया जाएगा: सामान्य आदेश (एन + 2) पेड़ बनाकर शुरू करें, जिसमें ऑर्डर एन + 1, एन, एन -1, ..., 2 , 1, 0. फिर, उन पेड़ों को एक ही नोड से दो बच्चों को काटने के बिना उनसे नोड्स काटकर जितना संभव हो उतना छोटा कर दें। यह ऑर्डर एन, एन -2, ..., 1, 0, और 0.
के साथ एक पेड़ छोड़ देता है अब हम यह निर्धारित करने के लिए एक पुनरावृत्ति संबंध लिख सकते हैं कि इन पेड़ों में कितने नोड्स हैं।
NC(0) = 1
NC(1) = 2
NC(n + 2) = NC(n) + NC(n - 1) + ... + NC(1) + NC(0) + NC(0) + 1
यहाँ, रूट नोड के लिए ही अंतिम +1 खातों: हम ऐसा करते हैं, तो हम निम्नलिखित है, जहां एन सी (एन) नोड्स है कि आदेश की एक पेड़ में हो सकता है n में सबसे छोटी संख्या का प्रतिनिधित्व करता मिलता है ।
अगर हम इन शर्तों बाहर का विस्तार, हम निम्नलिखित मिलती है:
NC(0) = 1
NC(1) = 2
NC(2) = NC(0) + NC(0) + 1 = 3
NC(3) = NC(1) + NC(0) + NC(0) + 1 = 5
NC(4) = NC(2) + NC(1) + NC(0) + NC(0) + 1 = 8
अगर आप ध्यान देंगे, इस ठीक दो पदों की भरपाई फिबोनैकी श्रृंखला है। दूसरे शब्दों में, इनमें से प्रत्येक पेड़ में कम से कम एफ एन + 2 नोड्स होना चाहिए, जहां एफ एन + 2 (एन + 2) nd फाइबोनैकी संख्या है।
तो इसे फिबोनाची ढेर क्यों कहा जाता है? क्योंकि ऑर्डर के प्रत्येक पेड़ में कम से कम F n + 2 नोड्स होना चाहिए!
आप उत्सुक हैं, तो the original paper on Fibonacci heaps इन छोटी संभव पेड़ की तस्वीरें है। यह देखने के लिए बहुत निफ्टी है!
आशा है कि इससे मदद मिलती है!
मैं एक अंतर्ज्ञानी स्पष्टीकरण देना चाहता हूं कि मेरे पास "आह!" पल के साथ
वृक्ष संरचनाएं ओ (लॉग एन) रनटाइम प्राप्त करती हैं क्योंकि वे अपनी ऊंचाइयों के मामले में वस्तुओं की घातीय संख्या को स्टोर करने में सक्षम हैं। बाइनरी पेड़ 2^एच स्टोर कर सकते हैं, त्रि-नारी पेड़ सामान्य^सामान्य रूप से x^h के लिए 3^एच स्टोर कर सकते हैं।
क्या x 2 से कम हो सकता है? यकीन है कि यह कर सकते हैं! जब तक x> 1 तक, हम अभी भी लॉग रनटाइम प्राप्त करते हैं और इसकी ऊंचाई के लिए तेजी से बड़ी संख्या में आइटम स्टोर करने की क्षमता प्राप्त करते हैं। लेकिन हम इस तरह के पेड़ कैसे बना सकते हैं? फिबोनाची ढेर एक डेटा संरचना है जहां x ≈ 1.62, या Golden Ratio है। जब भी हम गोल्डन अनुपात का सामना करते हैं, वहां फिबोनैकी संख्या कहीं छिपी हुई है ...
फिबोनाची ढेर वास्तव में पेड़ों का जंगल है। "समेकन" नामक प्रक्रिया के बाद, इनमें से प्रत्येक पेड़ उन वस्तुओं की एक अलग गिनती रखता है जो 2 की सटीक शक्तियां हैं। उदाहरण के लिए, यदि आपके फाइबोनैकी ढेर में 15 आइटम हैं, तो इसमें 4 पेड़ होंगे जो 1, 2, 4 और 8 आइटम क्रमशः इस तरह लग रही:
का विवरण "समेकन" प्रक्रिया प्रासंगिक नहीं है लेकिन संक्षेप में यह मूल रूप से एक ही डिग्री के जंगल में पेड़ unioning जब तक सभी पेड़ों अलग डिग्री (देखने के लिए एक cool visualization कोशिश है रहता है इन पेड़ों को कैसे बनाया जाता है)। जैसा कि आप किसी भी एन को 2 की सटीक शक्तियों के योग के रूप में लिख सकते हैं, यह कल्पना करना आसान है कि फाइबोनैकी ढेर के लिए समेकित पेड़ किसी भी एन के लिए कैसा दिखेंगे।
ठीक है, अब तक हम अभी भी फिबोनाची संख्याओं से कोई सीधा संबंध नहीं देखते हैं। वे तस्वीर में कहां आते हैं? वे वास्तव में बहुत ही विशेष मामले में दिखाई देते हैं और यह भी एक कुंजी है कि क्यों फाइबोनैकी ढेर डेक्रैस-कुंजी ऑपरेशन के लिए ओ (1) समय प्रदान कर सकता है। जब हम एक कुंजी कम करते हैं, तो नई कुंजी अभी भी माता-पिता की कुंजी से बड़ी है तो हमें कुछ और करने की आवश्यकता नहीं है क्योंकि न्यूनतम ढेर संपत्ति का उल्लंघन नहीं होता है। लेकिन अगर ऐसा नहीं होता है तो हम छोटे बच्चे को बड़े माता-पिता के नीचे दफन नहीं छोड़ सकते हैं और इसलिए हमें इसे कम करने और इसके बाहर एक नया पेड़ बनाने की जरूरत है। जाहिर है, हम प्रत्येक डिलीट के लिए ऐसा नहीं कर सकते हैं क्योंकि अन्यथा हम पेड़ों के साथ खत्म हो जाएंगे जो बहुत लंबा हैं और अब घातीय वस्तुएं नहीं हैं जिनका मतलब है कि निकालने के लिए ओ (लॉग एन) समय नहीं है। तो सवाल यह है कि हम किस नियम को स्थापित कर सकते हैं ताकि पेड़ की ऊंचाई के लिए घातीय वस्तुएं हों? चतुर अंतर्दृष्टि यह है:
We will allow each parent to loose up to one child. If there is a subsequent attempt to remove another child from same parent then we will cut that parent also out of that tree and put it in root list as tree of 1.
नियम से ऊपर यकीन है कि पेड़ अभी भी और भी बदतर मामले में अपनी ऊंचाई के लिए घातीय आइटम नहीं हैं बनाता है। बदतर मामला क्या है? बुरा मामला तब होता है जब हम प्रत्येक माता-पिता को एक बच्चे को ढीला करते हैं। अगर माता-पिता के पास> 1 बच्चा है तो हमारे पास छुटकारा पाने के लिए कोई विकल्प है। उस मामले में सबसे बड़े उप-बच्चे के साथ बच्चे से छुटकारा पाएं। तो उपरोक्त आरेख में, यदि आप प्रत्येक माता-पिता के लिए ऐसा करते हैं, तो आपके आकार 1, 1, 2 और 3 के पेड़ होंगे। यहां एक पैटर्न देखें? बस मस्ती के लिए, उपरोक्त आरेख में क्रम 4 (यानी 16 आइटम) के नए पेड़ को जोड़ें और अनुमान लगाएं कि प्रत्येक माता-पिता के लिए इस नियम को चलाने के बाद आपको क्या छोड़ा जाएगा: 5. हमारे पास एक फाइबोनैकी अनुक्रम है!
जैसा कि फाइबोनैकी अनुक्रम घातीय है, प्रत्येक पेड़ अभी भी घातीय वस्तुओं की संख्या को बरकरार रखता है और इस प्रकार एक्स्ट्राक्ट-मिन ऑपरेशन के लिए ओ (लॉग एन) रनटाइम का प्रबंधन करता है। हालांकि ध्यान दें कि डेक्रैस-कुंजी अब केवल ओ (1) लेता है। एक और अच्छी बात यह है कि आप फिबोनैकी संख्याओं के योग के रूप में किसी भी संख्या का प्रतिनिधित्व कर सकते हैं।उदाहरण के लिए, 32 = 21 + 8 + 3 जिसका अर्थ है कि यदि आपको फिबोनाची ढेर में 32 आइटम रखने की आवश्यकता है, तो आप क्रमशः 21, 8 और 3 आइटम वाले 3 पेड़ों का उपयोग करके ऐसा कर सकते हैं। हालांकि "समेकन" प्रक्रिया नोड्स के फिबोनाची संख्याओं के साथ पेड़ों का उत्पादन नहीं करती है। वे केवल तब होते हैं जब DECREASE-KEY या DELETE का यह खराब मामला होता है।
अतिरिक्त पठन
मुझे लगता है कि समस्या यह है, कि हम उनके रैंक के मामले में पेड़ के आकार है, लेकिन केवल एक सन्निकटन पता नहीं है। अगर हम आकारों को जान सकते हैं, तो हम उन्हें हफमैन कोडिंग में विलय कर सकते हैं और माता-पिता की हत्या के बिना चीजें ठीक हो जाएंगी। हालांकि पेड़ के आकार का ट्रैक रखना बहुत महंगा है। –
@ थॉमसएहले यह सही है। फाइबोनैकी ढेर को अपने माता-पिता से नोड्स काटने और केवल सीधे माता-पिता में जानकारी अपडेट करके अमूर्त ओ (1) कमी-चाबियों को अनुमति देने के लिए अनुकूलित किया जाता है। यदि आप अपने माता-पिता से नोड काटते हैं, तो आपको अपने सभी पूर्वजों पर उप-आकार का आकार अपडेट करना होगा, लेकिन इसमें Ω (लॉग एन) लगता है और ओ (1) कमी-कुंजी समय बाध्य करता है। – templatetypedef
मुझे आश्चर्य है कि किसी ने पेड़ के आकार के यादृच्छिक अनुमान को स्टोर करने का प्रयास किया है। फिर जब बच्चे को हटाते हैं, तो एल्गोरिदम अपने पूर्वजों के आकार को संभावना '1, 1/2, 1/4, ...' के साथ कम करता है, जो स्कीप्लिस्ट की तरह थोड़ा सा होता है। शायद यह पहले से ही कई अन्य ढेर की तुलना में अभ्यास में न तो सरल और न ही तेज है। –