फाइबोनैचि हीप

फाइबोनैचि हीप
Type	heap
Invented	1984
Invented by	माइकल एल. फ्रेडमैन और रॉबर्ट एंड्रे टार्जन
Time complexity in big O notation
Algorithm Average Worst case Insert Θ(1) Find-min Θ(1)   Delete-min O(log n)   Decrease-key Θ(1)   Merge Θ(1)

कंप्यूटर विज्ञान में, फाइबोनैचि हीप प्राथमिकता पंक्ति संचालन के लिए डेटा संरचना होती है, जिसमें हीप (डेटा संरचना) होती है| हीप-क्रमांक में दिए गए ट्री का संग्रह सम्मिलित होता है। इसमें बाइनरी हीप और द्विपद हीप सहित कई अन्य प्राथमिकता पंक्ति डेटा संरचनाओं की तुलना में श्रेष्ट परिशोधित विश्लेषण कार्यकारी समय होता है। माइकल एल. फ्रेडमैन और रॉबर्ट ई. टार्जन ने 1984 में फाइबोनैचि हीप विकसित किया और उन्हें 1987 में वैज्ञानिक पत्रिका में प्रकाशित किया था। फाइबोनैचि हीप का नाम फाइबोनैचि संख्याओं के नाम पर रखा गया है, जिनका उपयोग उनके चलने के समय के विश्लेषण में किया जाता है।

फाइबोनैचि हीप के लिए, अन्वेषण -न्यूनतम संचालन में स्थिर (बिग ओ अंकन(1)) परिशोधित समय लगता है। सम्मिलित करना और घटाना कुंजी संचालन में भी निरंतर परिशोधन समय में काम करते हैं।किसी तत्व को हटाना (अधिकांशतः न्यूनतम तत्व को हटाने के विशेष स्थिति में उपयोग किया जाता है) O(log n) परिशोधन समय में काम करता है, जहां n हीप का आकार होता है।इसका अर्थ यह है कि रिक्त डेटा संरचना से प्रारम्भ करके, सम्मिलित करने और कुंजी संचालन को कम करने और b विलोपन संचालन के किसी भी अनुक्रम में O(a + b log n) सबसे व्यर्थ स्थिति का समय लगता है, जहाँ n अधिकतम हीप आकार का होता है। द्विआधारी या द्विपद हीप में, संचालन के ऐसे अनुक्रम में O((a + b) log n) समय लगता है। इस प्रकार फाइबोनैचि हीप बाइनरी या द्विपद हीप से श्रेष्ट होता है जब b गैर-स्थिर कारक से छोटा होता है। दो फाइबोनैचि हीपों को निरंतर परिशोधन समय में विलय करना, द्विपद हीप के लघुगणकीय विलय समय में सुधार करना और बाइनरी हीपों में सुधार करना भी संभव है जो विलय को कुशलता से संभाल नहीं सकते हैं।

प्राथमिकता पंक्ति के लिए फाइबोनैचि हीप्स का उपयोग करने से महत्वपूर्ण कलन विधि के स्पर्शोन्मुख कार्यकारी समय में सुधार होता है, जैसे कि ग्राफ में दो नोड्स के मध्य सबसे छोटे पथ की गणना करने के लिए डिज्क्स्ट्रा का कलन विधि और अन्य मंद प्राथमिकता पंक्ति डेटा संरचनाओं का उपयोग करने वाले समान कलन विधि की तुलना में इसका उपयोग किया जाता है।

संरचना

चित्र 1. फाइबोनैचि हीप का उदाहरण। इसमें 0, 1 और 3 डिग्री के तीन ट्री हैं। तीन शीर्ष चिह्नित हैं (नीले रंग में दिखाए गए हैं)। इसलिए, हीप की क्षमता 9 (3 ट्री + 2 × (3 चिह्नित-शीर्ष)) है।

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

यघपि, कुछ बिंदु पर वांछित कार्यकारी समय प्राप्त करने के लिए हीप में क्रमांक प्रस्तुत करने की आवश्यकता होती है। विशेष रूप से, नोड्स की डिग्री (यहां डिग्री का अर्थ सीधे चाइल्ड की संख्या है) को अधिक कम रखा जाता है: प्रत्येक नोड में अधिकतम log n पर डिग्री होती है और डिग्री के नोड में निहित उपट्री का आकार कम से कम F_k+2 होता है, जहां F_k kth फाइबोनैचि संख्या होती है। यह इस नियम से प्राप्त होता है कि हम प्रत्येक गैर-रूट नोड के अधिकतम चाइल्ड को हटा सकते हैं। जब दूसरे चाइल्ड को हटा दिया जाता है, तो नोड को अपने पैरेंट से पृथक् होना पड़ता है और नए ट्री की रूट बन जाती है (डिग्री सीमा का प्रमाण नीचे देखें)। संचालन विलोपन न्यूनतम में ट्री की संख्या कम हो जाती है, जहां ट्री को साथ जोड़ा जाता है।

सुविधाजनक संरचना के परिणामस्वरूप, कुछ संचालन में अधिक समय लग सकता है जबकि अन्य बहुत शीघ्रता से किए जाते हैं। परिशोधित विश्लेषण विश्लेषण के लिए, हम संभावित विधि का उपयोग करते हैं, इसमें हम दिखाते हैं कि बहुत शीघ्र संचालन वास्तव में संचालन की तुलना में थोड़ा अधिक समय लेते हैं। इस अतिरिक्त समय को पश्चात् में जोड़ दिया जाता है और धीमे संचालन के वास्तविक चलने के समय से घटा दिया जाता है। पश्चात् में उपयोग के लिए बचाए गए समय की मात्रा को किसी भी क्षण संभावित फलन द्वारा मापा जाता है। फाइबोनैचि हीप की क्षमता किसके द्वारा दी गई है?

संभाव्यता = t + 2m

जहां t फाइबोनैचि हीप में ट्री की संख्या होती है, और m चिह्नित नोड्स की संख्या होती है। नोड को चिह्नित किया जाता है यदि उसके कम से कम चाइल्ड को हटा दिया गया हो क्योंकि इस नोड को दूसरे नोड का चाइल्ड बना दिया गया था (सभी रूट अचिह्नित हैं)। किसी संचालन के लिए परिशोधन समय वास्तविक समय के योग और क्षमता में अंतर के c गुना द्वारा दिया जाता है, जहां c स्थिरांक होता है (वास्तविक समय के लिए O अंकन में स्थिर कारकों से समरूप होने के लिए चुना गया है)।

इस प्रकार, हीप में प्रत्येक ट्री की रूट में समय की इकाई संग्रहीत होती है। समय की इस इकाई का उपयोग पश्चात् में परिशोधन समय 0 पर इस ट्री को दूसरे ट्री से जोड़ने के लिए किया जा सकता है। साथ ही, प्रत्येक चिह्नित नोड में समय की दो इकाइयाँ संग्रहीत होती हैं। एक का उपयोग नोड को उसके मूल से हटा ने के लिए किया जा सकता है। यदि ऐसा होता है, तो नोड रूट बन जाता है और समय की दूसरी इकाई किसी अन्य रूट की तरह इसमें संग्रहीत रहती है।

संचालन का कार्यान्वयन

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

संचालन न्यूनतम अन्वेषण अब तुच्छ हो गया है क्योंकि हम संकेतक को उस नोड पर रखते हैं जिसमें यह सम्मिलित होता है। यह हीप की क्षमता को नहीं परिवर्तित् करता है, इसलिए वास्तविक और परिशोधित लागत दोनों स्थिर होती हैं।

जैसा कि ऊपर उल्लेख किया गया है, विलय को मात्र दो हीपों के ट्री की रूट की सूचियों को जोड़कर प्रयुक्त किया जाता है। यह निरंतर समय में किया जा सकता है और क्षमता नहीं परिवर्तित होती है, जिससे फिर से निरंतर परिशोधन समय हो जाता है।

संचालन प्रविष्टि तत्व के साथ नया हीप बनाकर और विलय करके काम करता है। इसमें निरंतर समय लगता है, और क्षमता से बढ़ जाती है, क्योंकि ट्री की संख्या बढ़ जाती है। इस प्रकार परिशोधन लागत अभी भी स्थिर होता है।

संचालन उद्धरण न्यूनतम ('विलोपन न्यूनतम ' के समान) तीन चरणों में संचालित होता है। सर्वप्रथम हम न्यूनतम तत्व वाला मूल लेते हैं और उसे हटा देते हैं। इसके चाइल्ड नये ट्री की रूट बनेंगे। यदि चाइल्ड की संख्या d थी, तो सभी नई रूट को संसाधित करने में O(d) समय लगता है और क्षमता d−1 तक बढ़ जाती है। इसलिए, इस चरण का परिशोधन चलने का समय O(d) = O(log n) होता है।

यघपि, उद्धरण न्यूनतम संचालन को पूरा करने के लिए, हमें संकेतक को न्यूनतम कुंजी के साथ रूट पर अद्यतन करना होगा। दुर्भाग्य से n तक रूट हो सकती हैं जिनकी हमें जांच करने की आवश्यकता होती है। इसलिए दूसरे चरण में हम समान डिग्री की रूट को क्रमिक रूप से साथ जोड़कर रूट की संख्या कम करते हैं। जब दो रूट u और v की डिग्री समान होती है, तो हम उनमें से को दूसरे की चाइल्ड बनाते हैं जिसमें छोटी कुंजी वाला मूल बना रहे। इस प्रकार इसकी डिग्री से बढ़ जाती है। इसे तब तक दोहराया जाता है जब तक कि प्रत्येक रूट की भिन्न-भिन्न डिग्री न हो जाए। समान डिग्री के ट्री को कुशलतापूर्वक अन्वेषण ने के लिए हम O(log n) लंबाई की सरणी का उपयोग करते हैं जिसमें हम प्रत्येक डिग्री के मूल के लिए संकेतक रखते हैं। जब समान डिग्री का दूसरा रूट पाया जाता है, तो दोनों जुड़े होते हैं और सारणी को अद्यतन किया जाता है। वास्तविक चलने का समय O(log n + m) होता है जहां m दूसरे चरण के प्रारम्भ में रूट की संख्या होती है। अंत में हमारे पास अधिकतम O(log n) मूल होंगे (क्योंकि प्रत्येक की अलग डिग्री होती है)। इसलिए, इस चरण के पहले से लेकर इसके पश्चात् तक संभावित फलन में अंतर होता है: O(log n) − m, और परिशोधित चलने का समय अधिकतम O(log n + m) + c(O(log n) − m) होता है। c के पर्याप्त बड़े विकल्प के साथ, यह O(log n) तक सरल हो जाता है।

चित्र 2. न्यूनतम अर्क के पहले चरण के बाद चित्र 1 से फाइबोनैचि हीप। कुंजी 1 (न्यूनतम) वाला नोड हटा दिया गया था और उसके चाइल्ड को अलग ट्री के रूप में जोड़ा गया था।

चित्र 3. न्यूनतम अर्क पूरा होने के पश्चात् चित्र 1 से फाइबोनैचि हीप। सबसे पहले, नोड 3 और 6 एक साथ जुड़े हुए हैं। फिर परिणाम को नोड 2 पर निहित ट्री से जोड़ा जाता है। अंत में, नया न्यूनतम प्राप्त होता है।

चित्र 4. नोड 9 की कुंजी घटाकर 0 करने के बाद चित्र 1 से फाइबोनैचि हीप। इस नोड के साथ-साथ इसके दो चिह्नित पूर्वजों को 1 पर रूट वाले ट्री से काटा जाता है और नई जड़ों के रूप में रखा जाता है।

तीसरे चरण में हम प्रत्येक शेष मूल की जाँच करते हैं और न्यूनतम ज्ञात करते हैं। इसमें O(log n) समय लगता है और विभव नहीं परिवर्तितता है। इसलिए न्यूनतम निकालने का कुल परिशोधन समय O(log n) लगता है।

संचालन 'संक्षिप्त कुंजी' नोड लेता है, कुंजी को कम करता है और यदि हीप गुण का उल्लंघन हो जाता है (नई कुंजी मूल की कुंजी से छोटी है), तो नोड को उसके मूल से हटा दिया जाता है। यदि पैरेंट मूल नहीं है, तो इसे चिह्नित किया जाता है। यदि इसे पहले से ही चिह्नित किया गया है, तो इसे भी हटा दिया जाता है और इसके मूल को चिह्नित किया जाता है। हम तब तक ऊपर की ओर बढ़ते रहते हैं जब तक हम मूल या अचिह्नित नोड तक नहीं पहुंच जाते। अब हम न्यूनतम सूचक को घटे हुए मान पर स्थित करते हैं और इस प्रकार यह नया न्यूनतम होता है। इस प्रक्रिया में हम नए ट्री की कुछ संख्या, मान लीजिए k, बनाते हैं। संभवतः पहले ट्री को छोड़कर इनमें से प्रत्येक नए ट्री को मूल रूप से चिह्नित किया गया था, लेकिन रूट के रूप में यह अचिह्नित हो जाएगा। नोड चिह्नित किया जा सकता है. इसलिए, चिह्नित नोड्स की संख्या −(k − 1) −+ 1 − = − −k −2 से परिवर्तित जाती है। इन 2 परिवर्तनों को मिलाकर, संभावित 2(−k − 2) − −k − − −k − 4 − 4 से परिवर्तित की जाती है। वास्तविक समय कटिंग करने के लिए ओ(के) था, इसलिए (फिर से सी के पर्याप्त बड़े विकल्प के साथ) परिशोधन चलने का समय स्थिर है।

अंत में, संचालन विलोपन को हटाए जाने वाले तत्व की कुंजी को शून्य से अनंत तक कम करके कार्यान्वित किया जा सकता है, इस प्रकार इसे पूरे हीप के न्यूनतम में परिवर्तित दिया जा सकता है। फिर हम इसे हटाने के लिए उद्धरण न्यूनतम कहते हैं। इस संचालन का परिशोधन चलने का समय O(log n) लगता है।

डिग्री सीमा का प्रमाण

फाइबोनैचि हीप का परिशोधन प्रदर्शन किसी भी ट्री की रूट की डिग्री (चाइल्ड की संख्या) O(log n) पर निर्भर करता है, जहां n हीप का आकार होता है। यहां हम दिखाते हैं कि हीप में डिग्री d के किसी भी नोड x पर रूट (उप) ट्री का आकार कम से कम F_d+2 होना चाहिए, जहाँ F_k kth फाइबोनैचि संख्या होती है। डिग्री की बाध्यता इस और तथ्य (आसानी से प्रेरण द्वारा सिद्ध) से अनुसरण करती है $F_{d+2}\geq \varphi ^{d}$ सभी पूर्णांकों के लिए $d\geq 0$ होता, जहाँ $\varphi =(1+{\sqrt {5}})/2\doteq 1.618$ होता है। (तब हमारे पास $n\geq F_{d+2}\geq \varphi ^{d}$ होता है, और log को आधार पर ले जाता है $\varphi$, $d\leq \log _{\varphi }n$ आवश्यकता अनुसार दोनों पक्षों का देता है।)

हीप में कहीं किसी भी नोड x पर विचार करें (x को मुख्य ट्री में से की रूट होने की आवश्यकता नहीं है)। आकार(x) को x पर रूट ट्री के आकार के रूप में परिभाषित करें (x के संतति की संख्या, जिसमें स्वयं x भी सम्मिलित होता है)। हम x की ऊंचाई (x से संतति लीफ तक के सबसे लंबे सरल पथ की लंबाई) पर प्रेरण द्वारा सिद्ध करते हैं कि आकार (x) ≥ F_d+2 होता है, जहां d x की डिग्री होती है।

मुख्य स्थिति: यदि x की ऊंचाई 0 है, तो d = 0, और आकार(x) = 1 = F₂ होता है।

प्रेरक स्थिति: मान लीजिए x की ऊंचाई धनात्मक होती है और डिग्री d > 0 है। मान लीजिए y₁, y₂, ..., y_d के चाइल्ड हों, उन्हें उस समय के क्रम में अनुक्रमित किया जाता है जब वे वर्तमान में x (y) के चाइल्ड बने थे (y₁ सबसे प्रारंभिक होता है और y_d नवीनतम होता है),और मान लीजिए कि c₁, c₂, ..., c_d उनकी संबंधित डिग्री होती हैं। हम अनुरोध करते हैं कि 2 ≤ i ≤ d के साथ प्रत्येक i के लिए c_i ≥ i-2 : y_i को x का चाइल्ड बनाने से ठीक पहले, y₁,...,y_i−1 पहले से ही x के चाइल्ड थे, और इसलिए x के पास कम से कम डिग्री थी उस समय i−1थी। चूंकि ट्री तभी संयुक्त होते हैं जब उनकी रूट की डिग्री बराबर होती है, इसलिए यह अवश्य रहा होगा कि जब वह x का चाइल्ड बना तो यी के पास भी कम से कम i-1 डिग्री थी। उस समय से लेकर आज तक, y_i अधिकतम मात्र चाइल्ड लुप्त हो सकता है (जैसा कि अंकन प्रक्रिया द्वारा अश्वासन दिया गया है), और इसलिए इसकी वर्तमान डिग्री c_i कम से कम i−2 होती है। इससे 'वचन' सिद्ध होता है।

चूँकि सभी y_i की ऊँचाइयाँ x की तुलना में बिल्कुल न्यूनतम होती हैं, हम 'आकार'(y_i)≥ F_ci+2 ≥ F_(i−2)+2 = F_i. प्राप्त करने के लिए उन पर आगमनात्मक परिकल्पना प्रयुक्त कर सकते हैं। नोड्स x और y₁ प्रत्येक आकार (x) में कम से कम 1 का योगदान करते हैं, और इसलिए हमारे पास है

${\textbf {size}}(x)\geq 2+\sum _{i=2}^{d}{\textbf {size}}(y_{i})\geq 2+\sum _{i=2}^{d}F_{i}=1+\sum _{i=0}^{d}F_{i}.$

नियमित प्रेरण यह सिद्ध करता है $1+\sum _{i=0}^{d}F_{i}=F_{d+2}$ किसी के लिए $d\geq 0$ होता है, जो आकार (x) पर वांछित निम्नतर सीमा देता है।

सबसे व्यर्थ स्थिति

यघपि फाइबोनैचि हीप बहुत कुशल दिखते हैं, उनमें निम्नलिखित दो कमियाँ होती हैं:

1. जब इन्हें प्रयुक्त करने की बात आती है तो ये सम्मिश्र हो जाते हैं।
2. हीप के सैद्धांतिक रूप से कम कुशल रूपों की तुलना में वे व्यवहार में उतने कुशल नहीं होते हैं। अपने सरलतम संस्करण में उन्हें प्रति नोड चार संकेत के संग्रह और संचालन की आवश्यकता होती है, जबकि अन्य संरचनाओं में प्रति नोड मात्र दो या तीन संकेतकी आवश्यकता होती है, जैसे कि बाइनरी हीप, बाइनोमियल हीप, युग्मन हीप, ब्रोडल पंक्ति और रैंक पेयरिंग हीप।

यद्यपि रिक्त संरचना से प्रारम्भ होने वाले संचालन के अनुक्रम का कुल चलने का समय ऊपर दी गई सीमाओं से घिरा हुआ होता है, अनुक्रम में कुछ (बहुत कम) संचालन को पूरा होने में बहुत लंबा समय लग सकता है (विशेष रूप से हटाएं और हटाएं में न्यूनतम रैखिक चलने का समय सबसे व्यर्थ स्थिति में होता है)। इस कारण से फाइबोनैचि हीप और अन्य परिशोधित डेटा संरचनाएं वास्तविक समय कंप्यूटिंग के लिए उपयुक्त नहीं हो सकती हैं। ऐसी डेटा संरचना बनाना संभव है जिसका प्रदर्शन उतना ही व्यर्थ हो जितना कि फाइबोनैचि हीप का परिशोधित प्रदर्शन करना होता है। ऐसी ही संरचना, ब्रोडल पंक्ति ,, रचनाकार के शब्दों में, अधिक सम्मिश्र होती है और व्यवहार में प्रयुक्त नहीं होती है। 2012 में बनाया गया, कठोर फाइबोनैचि हीप रेफरी समान सबसे व्यर्थ स्थिति वाली सरल (ब्रोडल की तुलना में) संरचना होती है। सरल संरचना होने के पश्चात् भी, प्रयोगों से पता चलता है कि व्यवहार में कठोर फाइबोनैचि हीप अधिक सम्मिश्र ब्रोडल पंक्ति की तुलना में धीमा प्रदर्शन करता है और बुनियादी फाइबोनैचि हीप की तुलना में भी धीमा होता है।ड्रिस्कॉल एट अल के रन-शिथिलीकृत हीप विलय को छोड़कर सभी फाइबोनैचि हीप संचालन के लिए सबसे खराब स्थिति में अच्छा प्रदर्शन करते है।

चलने के समय का सारांश

Here are time complexities of various heap data structures. Function names assume a min-heap. For the meaning of "O(f)" and "Θ(f)" see Big O notation.

Operation	find-min	delete-min	insert	decrease-key	meld
Binary	Θ(1)	Θ(log n)	O(log n)	O(log n)	Θ(n)
Leftist	Θ(1)	Θ(log n)	Θ(log n)	O(log n)	Θ(log n)
Binomial	Θ(1)	Θ(log n)	Θ(1)	Θ(log n)	O(log n)
Fibonacci	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Pairing	Θ(1)	O(log n)	Θ(1)	o(log n)	Θ(1)
Brodal	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Rank-pairing	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Strict Fibonacci	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
2–3 heap	O(log n)	O(log n)	O(log n)	Θ(1)	?

व्यावहारिक विचार

प्रति नोड बड़ी संग्रह उपभोग और सभी परिचालनों पर उच्च स्थिर कारकों के कारण फाइबोनैचि हीप्स को व्यवहार में मंद होने के लिए जाना जाता है। वर्तमान के प्रयोगात्मक परिणामों से पता चलता है कि फाइबोनैचि हीप अपने अधिकांश पश्चात् के संजात की तुलना में व्यवहार में अधिक कुशल होते हैं, जिनमें भूकंप हीप, उल्लंघन हीप, सख्त फाइबोनैचि हीप, रैंक पेयरिंग हीप सम्मिलित होते हैं, यघपि युग्मन हीप या सरणी-आधारित हीप की तुलना में निम्न कुशल होते हैं।

बाहरी संबंध

• Java applet simulation of a Fibonacci heap
• MATLAB implementation of Fibonacci heap
• De-recursived and memory efficient C implementation of Fibonacci heap (free/libre software, CeCILL-B license)
• Ruby implementation of the Fibonacci heap (with tests)
• Pseudocode of the Fibonacci heap algorithm
• Various Java Implementations for Fibonacci heap