फाइबोनैचि हीप: Difference between revisions

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

Latest revision as of 19:27, 21 July 2023

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

फाइबोनैचि हीप के लिए, अन्वेषण -न्यूनतम संचालन में स्थिर (बिग ओ अंकन(1)) परिशोधित समय लगता है।^[1] सम्मिलित करना और घटाना कुंजी संचालन में भी निरंतर परिशोधन समय में काम करते हैं।^[2]किसी तत्व को हटाना (अधिकांशतः न्यूनतम तत्व को हटाने के विशेष स्थिति में उपयोग किया जाता है) O(log n) परिशोधन समय में काम करता है, जहां n हीप का आकार होता है।^[2]इसका अर्थ यह है कि रिक्त डेटा संरचना से प्रारम्भ करके, सम्मिलित करने और कुंजी संचालन को कम करने और 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₊₂ होता है, जहां 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₊₂ होना चाहिए, जहाँ 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₊₂ होता है, जहां 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₋₁ पहले से ही x के चाइल्ड थे, और इसलिए x के पास कम से कम डिग्री थी उस समय i−1थी। चूंकि ट्री तभी संयुक्त होते हैं जब उनकी रूट की डिग्री बराबर होती है, इसलिए यह अवश्य रहा होगा कि जब वह x का चाइल्ड बना तो यी के पास भी कम से कम i-1 डिग्री थी। उस समय से लेकर आज तक, y_i अधिकतम मात्र चाइल्ड लुप्त हो सकता है (जैसा कि अंकन प्रक्रिया द्वारा अश्वासन दिया गया है), और इसलिए इसकी वर्तमान डिग्री c_i कम से कम i−2 होती है। इससे 'वचन' सिद्ध होता है।

चूँकि सभी y_i की ऊँचाइयाँ x की तुलना में बिल्कुल न्यूनतम होती हैं, हम 'आकार'(y_i)≥ F_ci₊₂ ≥ 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) पर वांछित निम्नतर सीमा देता है।

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

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

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

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

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

Here are time complexities^[6] 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^[6]	Θ(1)	Θ(log n)	O(log n)	O(log n)	Θ(n)
Leftist	Θ(1)	Θ(log n)	Θ(log n)	O(log n)	Θ(log n)
Binomial^[6]^[7]	Θ(1)	Θ(log n)	Θ(1)^{[lower-alpha 1]}	Θ(log n)	O(log n)^{[lower-alpha 2]}
Fibonacci^[6]^[2]	Θ(1)	O(log n)^{[lower-alpha 1]}	Θ(1)	Θ(1)^{[lower-alpha 1]}	Θ(1)
Pairing^[8]	Θ(1)	O(log n)^{[lower-alpha 1]}	Θ(1)	o(log n)^{[lower-alpha 1]}^{[lower-alpha 3]}	Θ(1)
Brodal^[11]^{[lower-alpha 4]}	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Rank-pairing^[13]	Θ(1)	O(log n)^{[lower-alpha 1]}	Θ(1)	Θ(1)^{[lower-alpha 1]}	Θ(1)
Strict Fibonacci^[14]	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
2–3 heap^[15]	O(log n)	O(log n)^{[lower-alpha 1]}	O(log n)^{[lower-alpha 1]}	Θ(1)	?

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 ^1.8 Amortized time.
↑ n is the size of the larger heap.
↑ Lower bound of $\Omega (\log \log n),$ ^[9] upper bound of $O(2^{2{\sqrt {\log \log n}}}).$ ^[10]
↑ Brodal and Okasaki later describe a persistent variant with the same bounds except for decrease-key, which is not supported. Heaps with n elements can be constructed bottom-up in O(n).^[12]

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

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

संदर्भ

↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Chapter 20: Fibonacci Heaps". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 476–497. ISBN 0-262-03293-7. Third edition p. 518.
↑ ^2.0 ^2.1 ^2.2 Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. CiteSeerX 10.1.1.309.8927. doi:10.1145/28869.28874.
↑ Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. (1986). "The pairing heap: a new form of self-adjusting heap" (PDF). Algorithmica. 1 (1–4): 111–129. doi:10.1007/BF01840439. S2CID 23664143.
↑ Gerth Stølting Brodal (1996), "Worst-Case Efficient Priority Queues", Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics: 52–58, CiteSeerX 10.1.1.43.8133, ISBN 0-89871-366-8
↑ ^5.0 ^5.1 Larkin, Daniel; Sen, Siddhartha; Tarjan, Robert (2014). "प्राथमिकता कतारों का एक बैक-टू-बेसिक्स अनुभवजन्य अध्ययन". Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments: 61–72. arXiv:1403.0252. Bibcode:2014arXiv1403.0252L. doi:10.1137/1.9781611973198.7. ISBN 978-1-61197-319-8. S2CID 15216766.
↑ ^6.0 ^6.1 ^6.2 ^6.3 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
↑ "Binomial Heap | Brilliant Math & Science Wiki". brilliant.org (in English). Retrieved 2019-09-30.
↑ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, CiteSeerX 10.1.1.748.7812, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2
↑ Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214.
↑ Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX 10.1.1.549.471. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.
↑ Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
↑ Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN 0-471-46983-1.
↑ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
↑ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX 10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.
↑ Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12
↑ http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/FibonacciHeaps.pdf, p. 79

बाहरी संबंध

[amortized-8] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 ^1.8 Amortized time.

[meld-9] s the size of the larger heap.

[pairingdecreasekey-13] Lower bound of $\Omega (\log \log n),$ ^[9] upper bound of $O(2^{2{\sqrt {\log \log n}}}).$ ^[10]

[brodal-16] Brodal and Okasaki later describe a persistent variant with the same bounds except for decrease-key, which is not supported. Heaps with n elements can be constructed bottom-up in O(n).^[12]

[1] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Chapter 20: Fibonacci Heaps". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 476–497. ISBN 0-262-03293-7. Third edition p. 518.

[Fredman_And_Tarjan-2] 2.0 ^2.1 ^2.2 Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. CiteSeerX 10.1.1.309.8927. doi:10.1145/28869.28874.

[FSST-3] Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. (1986). "The pairing heap: a new form of self-adjusting heap" (PDF). Algorithmica. 1 (1–4): 111–129. doi:10.1007/BF01840439. S2CID 23664143.

[bare_url-4] Gerth Stølting Brodal (1996), "Worst-Case Efficient Priority Queues", Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics: 52–58, CiteSeerX 10.1.1.43.8133, ISBN 0-89871-366-8

[:0-5] 5.0 ^5.1 Larkin, Daniel; Sen, Siddhartha; Tarjan, Robert (2014). "प्राथमिकता कतारों का एक बैक-टू-बेसिक्स अनुभवजन्य अध्ययन". Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments: 61–72. arXiv:1403.0252. Bibcode:2014arXiv1403.0252L. doi:10.1137/1.9781611973198.7. ISBN 978-1-61197-319-8. S2CID 15216766.

[CLRS-6] 6.0 ^6.1 ^6.2 ^6.3 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.

[7] "Binomial Heap | Brilliant Math & Science Wiki". brilliant.org (in English). Retrieved 2019-09-30.

[Iacono-10] Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, CiteSeerX 10.1.1.748.7812, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2

[Fredman1999-11] Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214.

[12] Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX 10.1.1.549.471. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.

[14] Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58

[15] Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN 0-471-46983-1.

[17] Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.

[18] Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX 10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.

[19] Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12

[20] ttp://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/FibonacciHeaps.pdf, p. 79

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[lower-alpha 1]

[lower-alpha 2]

[8]

[lower-alpha 3]

[11]

[lower-alpha 4]

[13]

[14]

[15]

[9]

[10]

[12]

[16]

@@ Line 1: / Line 1: @@
 {{Short description|Data structure for priority queue operations}}
 {{Infobox data structure
-|name=Fibonacci heap
+|name=फाइबोनैचि हीप
 |type=[[Heap (data structure)|heap]]
-|invented_by=Michael L. Fredman and Robert Endre Tarjan
+|invented_by=माइकल एल. फ्रेडमैन और रॉबर्ट एंड्रे टार्जन
 |invented_year=1984
 |space_avg=
@@ Line 21: / Line 21: @@
 }}
-[[कंप्यूटर विज्ञान]] में, फाइबोनैचि हीप [[प्राथमिकता कतार]] संचालन के लिए [[डेटा संरचना]] है, जिसमें हीप (डेटा संरचना)|हीप-ऑर्डर किए गए पेड़ों का संग्रह शामिल होता है। इसमें [[ बाइनरी ढेर |बाइनरी ढेर]] और [[ द्विपद ढेर |द्विपद ढेर]] सहित कई अन्य प्राथमिकता कतार डेटा संरचनाओं की तुलना में बेहतर परिशोधित विश्लेषण रनिंग टाइम है। माइकल फ्रेडमैन|माइकल एल. फ्रेडमैन और रॉबर्ट टार्जन|रॉबर्ट ई. टार्जन ने 1984 में फाइबोनैचि ढेर विकसित किया और उन्हें 1987 में वैज्ञानिक पत्रिका में प्रकाशित किया। फाइबोनैचि ढेर का नाम [[फाइबोनैचि संख्या]]ओं के नाम पर रखा गया है, जिनका उपयोग उनके चलने के समय के विश्लेषण में किया जाता है।
+[[कंप्यूटर विज्ञान]] में, '''फाइबोनैचि हीप''' [[प्राथमिकता कतार|प्राथमिकता पंक्ति]] संचालन के लिए [[डेटा संरचना]] होती है, जिसमें हीप (डेटा संरचना) होती है| हीप-क्रमांक में दिए गए ट्री का संग्रह सम्मिलित होता है। इसमें [[ बाइनरी ढेर |बाइनरी हीप]] और [[ द्विपद ढेर |द्विपद हीप]] सहित कई अन्य प्राथमिकता पंक्ति डेटा संरचनाओं की तुलना में श्रेष्ट परिशोधित विश्लेषण कार्यकारी समय होता है। माइकल एल. फ्रेडमैन और रॉबर्ट ई. टार्जन ने 1984 में फाइबोनैचि हीप विकसित किया और उन्हें 1987 में वैज्ञानिक पत्रिका में प्रकाशित किया था। फाइबोनैचि हीप का नाम [[फाइबोनैचि संख्या]]ओं के नाम पर रखा गया है, जिनका उपयोग उनके चलने के समय के विश्लेषण में किया जाता है।
-फाइबोनैचि ढेर के लिए, खोज-न्यूनतम ऑपरेशन में स्थिर (''[[ बिग ओ अंकन ]]''(1)) परिशोधित समय लगता है।<ref>{{Introduction to Algorithms|2|chapter=Chapter 20: Fibonacci Heaps |pages=476&ndash;497}} Third edition p. 518.</ref> सम्मिलित करना और घटाना कुंजी संचालन भी निरंतर परिशोधन समय में काम करते हैं।<ref name="Fredman And Tarjan"/>किसी तत्व को हटाना (अक्सर न्यूनतम तत्व को हटाने के विशेष मामले में उपयोग किया जाता है) ओ (लॉग एन) परिशोधन समय में काम करता है, जहां एन ढेर का आकार है।<ref name="Fredman And Tarjan"/>इसका मतलब यह है कि खाली डेटा संरचना से शुरू करके, सम्मिलित करने और कुंजी संचालन को कम करने और बी डिलीट संचालन के किसी भी अनुक्रम में ओ (ए + बी लॉग एन) सबसे खराब स्थिति का समय लगेगा, जहां एन अधिकतम ढेर आकार है। द्विआधारी या द्विपद ढेर में, संचालन के ऐसे अनुक्रम में O((a + b) log n) समय लगेगा। इस प्रकार फाइबोनैचि ढेर बाइनरी या द्विपद ढेर से बेहतर होता है जब बी गैर-स्थिर कारक से छोटा होता है। दो फाइबोनैचि ढेरों को निरंतर परिशोधन समय में मर्ज करना, द्विपद ढेर के लघुगणकीय विलय समय में सुधार करना और बाइनरी ढेरों में सुधार करना भी संभव है जो मर्ज को कुशलता से संभाल नहीं सकते हैं।
+फाइबोनैचि हीप के लिए, अन्वेषण -न्यूनतम संचालन में स्थिर (''[[ बिग ओ अंकन |बिग ओ अंकन]]''(1)) परिशोधित समय लगता है।<ref>{{Introduction to Algorithms|2|chapter=Chapter 20: Fibonacci Heaps |pages=476&ndash;497}} Third edition p. 518.</ref> सम्मिलित करना और घटाना कुंजी संचालन में भी निरंतर परिशोधन समय में काम करते हैं।<ref name="Fredman And Tarjan"/>किसी तत्व को हटाना (अधिकांशतः न्यूनतम तत्व को हटाने के विशेष स्थिति में उपयोग किया जाता है) ''O''(log ''n)'' परिशोधन समय में काम करता है, जहां ''n'' हीप का आकार होता है।<ref name="Fredman And Tarjan"/>इसका अर्थ यह है कि रिक्त डेटा संरचना से प्रारम्भ करके, सम्मिलित करने और कुंजी संचालन को कम करने और ''b'' विलोपन संचालन के किसी भी अनुक्रम में ''O''(''a'' + ''b'' log ''n'') सबसे व्यर्थ स्थिति का समय लगता है, जहाँ ''n'' अधिकतम हीप आकार का होता है। द्विआधारी या द्विपद हीप में, संचालन के ऐसे अनुक्रम में O((a + b) log n) समय लगता है। इस प्रकार फाइबोनैचि हीप बाइनरी या द्विपद हीप से श्रेष्ट होता है जब ''b'' गैर-स्थिर कारक से छोटा होता है। दो फाइबोनैचि हीपों को निरंतर परिशोधन समय में विलय करना, द्विपद हीप के लघुगणकीय विलय समय में सुधार करना और बाइनरी हीपों में सुधार करना भी संभव है जो विलय को कुशलता से संभाल नहीं सकते हैं।
-प्राथमिकता कतारों के लिए फाइबोनैचि हीप्स का उपयोग करने से महत्वपूर्ण एल्गोरिदम के एसिम्प्टोटिक रनिंग समय में सुधार होता है, जैसे कि ग्राफ में दो नोड्स के बीच सबसे छोटे पथ की गणना करने के लिए डिज्क्स्ट्रा का एल्गोरिदम, अन्य धीमी प्राथमिकता कतार डेटा संरचनाओं का उपयोग करने वाले समान एल्गोरिदम की तुलना में।
+प्राथमिकता पंक्ति के लिए फाइबोनैचि हीप्स का उपयोग करने से महत्वपूर्ण कलन विधि के स्पर्शोन्मुख कार्यकारी समय में सुधार होता है, जैसे कि ग्राफ में दो नोड्स के मध्य सबसे छोटे पथ की गणना करने के लिए डिज्क्स्ट्रा का कलन विधि और अन्य मंद प्राथमिकता पंक्ति डेटा संरचनाओं का उपयोग करने वाले समान कलन विधि की तुलना में इसका उपयोग किया जाता है।
 == संरचना ==
-[[Image:Fibonacci heap.png|thumbnail|upright=1.05|चित्र 1. फाइबोनैचि ढेर का उदाहरण। इसमें 0, 1 और 3 डिग्री के तीन पेड़ हैं। तीन शीर्ष चिह्नित हैं (नीले रंग में दिखाए गए हैं)। इसलिए, ढेर की क्षमता 9 (3 पेड़ + 2 × (3 चिह्नित-शीर्ष)) है।]]फाइबोनैचि हीप ट्री डेटा संरचनाओं का संग्रह है जो न्यूनतम-हीप संपत्ति को संतुष्ट करता है, अर्थात, बच्चे की कुंजी हमेशा माता-पिता की कुंजी से अधिक या उसके बराबर होती है। इसका तात्पर्य यह है कि न्यूनतम कुंजी हमेशा किसी पेड़ की जड़ पर होती है। द्विपद ढेर की तुलना में, फाइबोनैचि ढेर की संरचना अधिक लचीली होती है। पेड़ों का कोई निर्धारित आकार नहीं होता है और चरम स्थिति में ढेर में प्रत्येक तत्व अलग पेड़ में हो सकता है। यह लचीलापन कुछ कार्यों को [[आलसी मूल्यांकन]] तरीके से निष्पादित करने की अनुमति देता है, जिससे काम को बाद के संचालन के लिए स्थगित कर दिया जाता है। उदाहरण के लिए, ढेरों का विलय केवल पेड़ों की दो सूचियों को जोड़कर किया जाता है, और ऑपरेशन कमी कुंजी कभी-कभी अपने मूल से नोड को काट देती है और नया पेड़ बनाती है।
+[[Image:Fibonacci heap.png|thumbnail|upright=1.05|चित्र 1. फाइबोनैचि हीप का उदाहरण। इसमें 0, 1 और 3 डिग्री के तीन ट्री हैं। तीन शीर्ष चिह्नित हैं (नीले रंग में दिखाए गए हैं)। इसलिए, हीप की क्षमता 9 (3 ट्री + 2 × (3 चिह्नित-शीर्ष)) है।]]फाइबोनैचि हीप ट्री डेटा संरचनाओं का संग्रह होता है जो न्यूनतम-हीप गुण को संतुष्ट करता है, अर्थात, चाइल्ड की कुंजी हमेशा पैरेंट की कुंजी से अधिक या उसके बराबर होती है। इसका तात्पर्य यह है कि न्यूनतम कुंजी हमेशा किसी ट्री की रूट पर होती है। द्विपद हीप की तुलना में, फाइबोनैचि हीप की संरचना अधिक तन्यता होती है। ट्री का कोई निर्धारित आकार नहीं होता है और चरम स्थिति में हीप में प्रत्येक तत्व भिन्न ट्री में हो सकता है। यह तन्यता कुछ कार्यों को [[आलसी मूल्यांकन]] तरीके से निष्पादित करने की अनुमति देता है, जिससे काम को पश्चात् के संचालन के लिए स्थगित कर दिया जाता है। उदाहरण के लिए, हीपों का विलय मात्र ट्री की दो सूचियों को जोड़कर किया जाता है, और संचालन कमी कुंजी कभी-कभी अपने मूल से नोड को हटा देती है और नया ट्री निर्मित करता है।
-हालाँकि, कुछ बिंदु पर वांछित रनिंग समय प्राप्त करने के लिए ढेर में ऑर्डर पेश करने की आवश्यकता होती है। विशेष रूप से, नोड्स की डिग्री (यहां डिग्री का मतलब सीधे बच्चों की संख्या है) को काफी कम रखा गया है: प्रत्येक नोड में अधिकतम लॉग एन पर डिग्री होती है और डिग्री के नोड में निहित उपट्री का आकार कम से कम एफ होता है<sub>''k''+2</sub>, जहां एफ<sub>k</sub>kth फाइबोनैचि संख्या है. यह इस नियम से प्राप्त होता है कि हम प्रत्येक गैर-रूट नोड के अधिकतम बच्चे को काट सकते हैं। जब दूसरे बच्चे को काटा जाता है, तो नोड को अपने माता-पिता से अलग होना पड़ता है और नए पेड़ की जड़ बन जाती है (डिग्री सीमा का प्रमाण नीचे देखें)। ऑपरेशन डिलीट मिनिमम में पेड़ों की संख्या कम हो जाती है, जहां पेड़ों को साथ जोड़ा जाता है।
+यघपि, कुछ बिंदु पर वांछित कार्यकारी समय प्राप्त करने के लिए हीप में क्रमांक प्रस्तुत करने की आवश्यकता होती है। विशेष रूप से, नोड्स की डिग्री (यहां डिग्री का अर्थ सीधे चाइल्ड की संख्या है) को अधिक कम रखा जाता है: प्रत्येक नोड में अधिकतम ''log n'' पर डिग्री होती है और डिग्री के नोड में निहित उपट्री का आकार कम से कम ''F<sub>k</sub>''<sub>+2</sub> होता है, जहां ''F<sub>k</sub>'' kth फाइबोनैचि संख्या होती है। यह इस नियम से प्राप्त होता है कि हम प्रत्येक गैर-रूट नोड के अधिकतम चाइल्ड को हटा सकते हैं। जब दूसरे चाइल्ड को हटा दिया जाता है, तो नोड को अपने पैरेंट से पृथक् होना पड़ता है और नए ट्री की रूट बन जाती है (डिग्री सीमा का प्रमाण नीचे देखें)। संचालन विलोपन न्यूनतम में ट्री की संख्या कम हो जाती है, जहां ट्री को साथ जोड़ा जाता है।
-आरामदायक संरचना के परिणामस्वरूप, कुछ ऑपरेशनों में लंबा समय लग सकता है जबकि अन्य बहुत जल्दी किए जाते हैं। परिशोधित विश्लेषण विश्लेषण के लिए, हम [[संभावित विधि]] का उपयोग करते हैं, इसमें हम दिखावा करते हैं कि बहुत तेज़ संचालन वास्तव में करने की तुलना में थोड़ा अधिक समय लेते हैं। इस अतिरिक्त समय को बाद में जोड़ दिया जाता है और धीमे संचालन के वास्तविक चलने के समय से घटा दिया जाता है। बाद में उपयोग के लिए बचाए गए समय की मात्रा को किसी भी क्षण संभावित फ़ंक्शन द्वारा मापा जाता है। फाइबोनैचि ढेर की क्षमता किसके द्वारा दी गई है?
+सुविधाजनक संरचना के परिणामस्वरूप, कुछ संचालन में अधिक समय लग सकता है जबकि अन्य बहुत शीघ्रता से किए जाते हैं। परिशोधित विश्लेषण विश्लेषण के लिए, हम [[संभावित विधि]] का उपयोग करते हैं, इसमें हम दिखाते हैं कि बहुत शीघ्र संचालन वास्तव में संचालन की तुलना में थोड़ा अधिक समय लेते हैं। इस अतिरिक्त समय को पश्चात् में जोड़ दिया जाता है और धीमे संचालन के वास्तविक चलने के समय से घटा दिया जाता है। पश्चात् में उपयोग के लिए बचाए गए समय की मात्रा को किसी भी क्षण संभावित फलन द्वारा मापा जाता है। फाइबोनैचि हीप की क्षमता किसके द्वारा दी गई है?
 :संभाव्यता = t + 2m
-जहां t फाइबोनैचि ढेर में पेड़ों की संख्या है, और m चिह्नित नोड्स की संख्या है। नोड को चिह्नित किया जाता है यदि उसके कम से कम बच्चे को काट दिया गया हो क्योंकि इस नोड को दूसरे नोड का बच्चा बना दिया गया था (सभी जड़ें अचिह्नित हैं)।
+जहां t फाइबोनैचि हीप में ट्री की संख्या होती है, और m चिह्नित नोड्स की संख्या होती है। नोड को चिह्नित किया जाता है यदि उसके कम से कम चाइल्ड को हटा दिया गया हो क्योंकि इस नोड को दूसरे नोड का चाइल्ड बना दिया गया था (सभी रूट अचिह्नित हैं)। किसी संचालन के लिए परिशोधन समय वास्तविक समय के योग और क्षमता में अंतर के ''c'' गुना द्वारा दिया जाता है, जहां ''c'' स्थिरांक होता है (वास्तविक समय के लिए ''O'' अंकन में स्थिर कारकों से समरूप होने के लिए चुना गया है)।
-किसी ऑपरेशन के लिए परिशोधन समय वास्तविक समय के योग और क्षमता में अंतर के सी गुना द्वारा दिया जाता है, जहां सी स्थिरांक है (वास्तविक समय के लिए ओ नोटेशन में स्थिर कारकों से मेल खाने के लिए चुना गया है)।
-इस प्रकार, ढेर में प्रत्येक पेड़ की जड़ में समय की इकाई संग्रहीत होती है। समय की इस इकाई का उपयोग बाद में परिशोधन समय 0 पर इस पेड़ को दूसरे पेड़ से जोड़ने के लिए किया जा सकता है। साथ ही, प्रत्येक चिह्नित नोड में समय की दो इकाइयाँ संग्रहीत होती हैं। का उपयोग नोड को उसके मूल से काटने के लिए किया जा सकता है। यदि ऐसा होता है, तो नोड रूट बन जाता है और समय की दूसरी इकाई किसी अन्य रूट की तरह इसमें संग्रहीत रहेगी।
+इस प्रकार, हीप में प्रत्येक ट्री की रूट में समय की इकाई संग्रहीत होती है। समय की इस इकाई का उपयोग पश्चात् में परिशोधन समय 0 पर इस ट्री को दूसरे ट्री से जोड़ने के लिए किया जा सकता है। साथ ही, प्रत्येक चिह्नित नोड में समय की दो इकाइयाँ संग्रहीत होती हैं। एक का उपयोग नोड को उसके मूल से हटा ने के लिए किया जा सकता है। यदि ऐसा होता है, तो नोड रूट बन जाता है और समय की दूसरी इकाई किसी अन्य रूट की तरह इसमें संग्रहीत रहती है।
 == संचालन का कार्यान्वयन ==
-तेजी से विलोपन और संयोजन की अनुमति देने के लिए, सभी पेड़ों की जड़ों को गोलाकार [[दोगुनी लिंक्ड सूची]] का उपयोग करके जोड़ा जाता है। प्रत्येक नोड के बच्चे भी ऐसी सूची का उपयोग करके जुड़े हुए हैं। प्रत्येक नोड के लिए, हम उसके बच्चों की संख्या बनाए रखते हैं और क्या नोड चिह्नित है। इसके अलावा, हम न्यूनतम कुंजी वाले रूट पर पॉइंटर बनाए रखते हैं।
+शीघ्रता से विलोपन और संयोजन की अनुमति देने के लिए, सभी ट्री की रूट को गोलाकार [[दोगुनी लिंक्ड सूची|दोगुनी संबद्ध सूची]] का उपयोग करके जोड़ा जाता है। प्रत्येक नोड के चाइल्ड भी ऐसी सूची का उपयोग करके जुड़े हुए होते हैं। प्रत्येक नोड के लिए, हम उसके चाइल्ड की संख्या बनाए रखते हैं और क्या नोड चिह्नित है। इसके अतिरिक्त, हम न्यूनतम कुंजी वाले रूट पर बिंदु बनाए रखते हैं।
-ऑपरेशन फाइंड मिनिमम अब तुच्छ हो गया है क्योंकि हम पॉइंटर को उस नोड पर रखते हैं जिसमें यह शामिल है। यह ढेर की क्षमता को नहीं बदलता है, इसलिए वास्तविक और परिशोधित लागत दोनों स्थिर हैं।
+संचालन '''न्यूनतम अन्वेषण''' अब तुच्छ हो गया है क्योंकि हम संकेतक को उस नोड पर रखते हैं जिसमें यह सम्मिलित होता है। यह हीप की क्षमता को नहीं परिवर्तित् करता है, इसलिए वास्तविक और परिशोधित लागत दोनों स्थिर होती हैं।
-जैसा कि ऊपर उल्लेख किया गया है, मर्ज को केवल दो ढेरों के पेड़ की जड़ों की सूचियों को जोड़कर लागू किया जाता है। यह निरंतर समय में किया जा सकता है और क्षमता नहीं बदलती है, जिससे फिर से निरंतर परिशोधन समय हो जाता है।
+जैसा कि ऊपर उल्लेख किया गया है, विलय को मात्र दो हीपों के ट्री की रूट की सूचियों को जोड़कर प्रयुक्त किया जाता है। यह निरंतर समय में किया जा सकता है और क्षमता नहीं परिवर्तित होती है, जिससे फिर से निरंतर परिशोधन समय हो जाता है।
-ऑपरेशन इंसर्ट तत्व के साथ नया ढेर बनाकर और मर्ज करके काम करता है। इसमें निरंतर समय लगता है, और क्षमता से बढ़ जाती है, क्योंकि पेड़ों की संख्या बढ़ जाती है। इस प्रकार परिशोधन लागत अभी भी स्थिर है।
+संचालन प्रविष्टि तत्व के साथ नया हीप बनाकर और विलय करके काम करता है। इसमें निरंतर समय लगता है, और क्षमता से बढ़ जाती है, क्योंकि ट्री की संख्या बढ़ जाती है। इस प्रकार परिशोधन लागत अभी भी स्थिर होता है।
-ऑपरेशन एक्सट्रेक्ट मिनिमम ('डिलीट मिनिमम' के समान) तीन चरणों में संचालित होता है। सबसे पहले हम न्यूनतम तत्व वाला मूल लेते हैं और उसे हटा देते हैं। इसके बच्चे नये वृक्षों की जड़ें बनेंगे। यदि बच्चों की संख्या ''d'' थी, तो सभी नई जड़ों को संसाधित करने में ''O''(''d'') समय लगता है और क्षमता ''d''−1 तक बढ़ जाती है। इसलिए, इस चरण का परिशोधन चलने का समय ''O''(''d'') = ''O''(log ''n'') है।
+संचालन उद्धरण न्यूनतम ('विलोपन न्यूनतम ' के समान) तीन चरणों में संचालित होता है। सर्वप्रथम हम न्यूनतम तत्व वाला मूल लेते हैं और उसे हटा देते हैं। इसके चाइल्ड नये ट्री की रूट बनेंगे। यदि चाइल्ड की संख्या ''d'' थी, तो सभी नई रूट को संसाधित करने में ''O''(''d'') समय लगता है और क्षमता ''d''−1 तक बढ़ जाती है। इसलिए, इस चरण का परिशोधन चलने का समय ''O''(''d'') = ''O''(log ''n'') होता है।
-हालाँकि, एक्सट्रेक्ट मिनिमम ऑपरेशन को पूरा करने के लिए, हमें पॉइंटर को न्यूनतम कुंजी के साथ रूट पर अपडेट करना होगा। दुर्भाग्य से ''एन'' तक जड़ें हो सकती हैं जिनकी हमें जांच करने की आवश्यकता है। इसलिए दूसरे चरण में हम समान डिग्री की जड़ों को क्रमिक रूप से साथ जोड़कर जड़ों की संख्या कम करते हैं। जब दो जड़ों ''u'' और ''v'' की डिग्री समान होती है, तो हम उनमें से को दूसरे की संतान बनाते हैं ताकि छोटी कुंजी वाला मूल बना रहे। इसकी डिग्री से बढ़ जाएगी. इसे तब तक दोहराया जाता है जब तक कि प्रत्येक जड़ की अलग-अलग डिग्री न हो जाए। समान डिग्री के पेड़ों को कुशलतापूर्वक खोजने के लिए हम ''ओ'' (लॉग ''एन'') लंबाई की सरणी का उपयोग करते हैं जिसमें हम प्रत्येक डिग्री के मूल के लिए संकेतक रखते हैं। जब समान डिग्री का दूसरा रूट पाया जाता है, तो दोनों जुड़े होते हैं और एरे को अपडेट किया जाता है। वास्तविक चलने का समय ''O'' (लॉग ''n'' + ''m'') है जहां ''m'' दूसरे चरण की शुरुआत में जड़ों की संख्या है। अंत में हमारे पास अधिकतम ''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'') तक सरल हो जाता है।
 {|style="margin: 0 auto;"
-  | [[Image:Fibonacci heap extractmin1.png|170px|thumb|right|Figure 2. Fibonacci heap from Figure 1 after first phase of extract minimum. Node with key 1 (the minimum) was deleted and its children were added as separate trees.]]
+  | [[Image:Fibonacci heap extractmin1.png|170px|thumb|right|चित्र 2. न्यूनतम अर्क के पहले चरण के बाद चित्र 1 से फाइबोनैचि हीप। कुंजी 1 (न्यूनतम) वाला नोड हटा दिया गया था और उसके चाइल्ड को अलग ट्री के रूप में जोड़ा गया था।]]
-  | [[Image:Fibonacci heap extractmin2.png|130px|thumb|Figure 3. Fibonacci heap from Figure 1 after extract minimum is completed. First, nodes 3 and 6 are linked together. Then the result is linked with tree rooted at node 2. Finally, the new minimum is found.]]
+  | [[Image:Fibonacci heap extractmin2.png|130px|thumb|चित्र 3. न्यूनतम अर्क पूरा होने के पश्चात् चित्र 1 से फाइबोनैचि हीप। सबसे पहले, नोड 3 और 6 एक साथ जुड़े हुए हैं। फिर परिणाम को नोड 2 पर निहित ट्री से जोड़ा जाता है। अंत में, नया न्यूनतम प्राप्त होता है। ]]
-  | [[Image:Fibonacci heap-decreasekey.png|250px|thumb|right|Figure 4. Fibonacci heap from Figure 1 after decreasing key of node 9 to 0. This node as well as its two marked ancestors are cut from the tree rooted at 1 and placed as new roots.]]
+  | [[Image:Fibonacci heap-decreasekey.png|250px|thumb|right|चित्र 4. नोड 9 की कुंजी घटाकर 0 करने के बाद चित्र 1 से फाइबोनैचि हीप। इस नोड के साथ-साथ इसके दो चिह्नित पूर्वजों को 1 पर रूट वाले ट्री से काटा जाता है और नई जड़ों के रूप में रखा जाता है।]]
   |}
-तीसरे चरण में हम प्रत्येक शेष मूल की जाँच करते हैं और न्यूनतम ज्ञात करते हैं। इसमें O(log n) समय लगता है और विभव नहीं बदलता है। इसलिए न्यूनतम निकालने का कुल परिशोधन समय O(लॉग एन) है।
+तीसरे चरण में हम प्रत्येक शेष मूल की जाँच करते हैं और न्यूनतम ज्ञात करते हैं। इसमें O(log n) समय लगता है और विभव नहीं परिवर्तितता है। इसलिए न्यूनतम निकालने का कुल परिशोधन समय O(log n) लगता है।
-ऑपरेशन 'कमी कुंजी' नोड लेगा, कुंजी को कम करेगा और यदि ढेर संपत्ति का उल्लंघन हो जाता है (नई कुंजी मूल की कुंजी से छोटी है), तो नोड को उसके मूल से काट दिया जाता है। यदि अभिभावक मूल नहीं है, तो इसे चिह्नित किया जाता है। यदि इसे पहले से ही चिह्नित किया गया है, तो इसे भी काट दिया जाता है और इसके मूल को चिह्नित किया जाता है। हम तब तक ऊपर की ओर बढ़ते रहते हैं जब तक हम मूल या अचिह्नित नोड तक नहीं पहुंच जाते। अब हम न्यूनतम सूचक को घटे हुए मान पर सेट करते हैं यदि यह नया न्यूनतम है। इस प्रक्रिया में हम नए पेड़ों की कुछ संख्या, मान लीजिए k, बनाते हैं। संभवतः पहले पेड़ को छोड़कर इनमें से प्रत्येक नए पेड़ को मूल रूप से चिह्नित किया गया था, लेकिन जड़ के रूप में यह अचिह्नित हो जाएगा। नोड चिह्नित किया जा सकता है. इसलिए, चिह्नित नोड्स की संख्या −(k − 1) −+ 1 − = − −k −2 से बदल जाती है। इन 2 परिवर्तनों को मिलाकर, संभावित 2(−k − 2) − −k − − −k − 4 − 4 से बदल जाती है। वास्तविक समय कटिंग करने के लिए ओ(के) था, इसलिए (फिर से सी के पर्याप्त बड़े विकल्प के साथ) परिशोधन चलने का समय स्थिर है।
+संचालन 'संक्षिप्त कुंजी' नोड लेता है, कुंजी को कम करता है और यदि हीप गुण का उल्लंघन हो जाता है (नई कुंजी मूल की कुंजी से छोटी है), तो नोड को उसके मूल से हटा दिया जाता है। यदि पैरेंट मूल नहीं है, तो इसे चिह्नित किया जाता है। यदि इसे पहले से ही चिह्नित किया गया है, तो इसे भी हटा दिया जाता है और इसके मूल को चिह्नित किया जाता है। हम तब तक ऊपर की ओर बढ़ते रहते हैं जब तक हम मूल या अचिह्नित नोड तक नहीं पहुंच जाते। अब हम न्यूनतम सूचक को घटे हुए मान पर स्थित करते हैं और इस प्रकार यह नया न्यूनतम होता है। इस प्रक्रिया में हम नए ट्री की कुछ संख्या, मान लीजिए k, बनाते हैं। संभवतः पहले ट्री को छोड़कर इनमें से प्रत्येक नए ट्री को मूल रूप से चिह्नित किया गया था, लेकिन रूट के रूप में यह अचिह्नित हो जाएगा। नोड चिह्नित किया जा सकता है. इसलिए, चिह्नित नोड्स की संख्या −(k − 1) −+ 1 − = − −k −2 से परिवर्तित जाती है। इन 2 परिवर्तनों को मिलाकर, संभावित 2(−k − 2) − −k − − −k − 4 − 4 से परिवर्तित की जाती है। वास्तविक समय कटिंग करने के लिए ओ(के) था, इसलिए (फिर से सी के पर्याप्त बड़े विकल्प के साथ) परिशोधन चलने का समय स्थिर है।
-अंत में, ऑपरेशन 'डिलीट' को हटाए जाने वाले तत्व की कुंजी को शून्य से अनंत तक कम करके कार्यान्वित किया जा सकता है, इस प्रकार इसे पूरे ढेर के न्यूनतम में बदल दिया जा सकता है। फिर हम इसे हटाने के लिए एक्सट्रैक्ट मिनिमम कहते हैं। इस ऑपरेशन का परिशोधन चलने का समय O(लॉग एन) है।
+अंत में, संचालन '''विलोपन''' को हटाए जाने वाले तत्व की कुंजी को शून्य से अनंत तक कम करके कार्यान्वित किया जा सकता है, इस प्रकार इसे पूरे हीप के न्यूनतम में परिवर्तित दिया जा सकता है। फिर हम इसे हटाने के लिए उद्धरण न्यूनतम कहते हैं। इस संचालन का परिशोधन चलने का समय ''O''(log ''n'') लगता है।
 ==डिग्री सीमा का प्रमाण==
-फाइबोनैचि ढेर का परिशोधन प्रदर्शन किसी भी पेड़ की जड़ की डिग्री (बच्चों की संख्या) ओ (लॉग एन) पर निर्भर करता है, जहां एन ढेर का आकार है। यहां हम दिखाते हैं कि ढेर में डिग्री डी के किसी भी नोड x पर जड़े (उप) पेड़ का आकार कम से कम एफ होना चाहिए<sub>d</sub><sub>+2</sub>, जहां एफ<sub>k</sub>kth फाइबोनैचि संख्या है. डिग्री की बाध्यता इस और तथ्य (आसानी से प्रेरण द्वारा सिद्ध) से अनुसरण करती है <math>F_{d+2} \ge \varphi^d</math> सभी पूर्णांकों के लिए <math>d\ge 0</math>, कहाँ <math>\varphi = (1+\sqrt 5)/2 \doteq 1.618</math>. (तब हमारे पास है <math>n \ge F_{d+2} \ge \varphi^d</math>, और लॉग को आधार पर ले जाना <math>\varphi</math> दोनों पक्षों का देता है <math>d\le \log_{\varphi} n</math> आवश्यकता अनुसार।)
+फाइबोनैचि हीप का परिशोधन प्रदर्शन किसी भी ट्री की रूट की डिग्री (चाइल्ड की संख्या) ''O''(log ''n'') पर निर्भर करता है, जहां ''n'' हीप का आकार होता है। यहां हम दिखाते हैं कि हीप में डिग्री ''d'' के किसी भी नोड x पर रूट (उप) ट्री का आकार कम से कम ''F<sub>d</sub>''<sub>+2</sub> होना चाहिए, जहाँ ''F<sub>k</sub>'' kth फाइबोनैचि संख्या होती है। डिग्री की बाध्यता इस और तथ्य (आसानी से प्रेरण द्वारा सिद्ध) से अनुसरण करती है <math>F_{d+2} \ge \varphi^d</math> सभी पूर्णांकों के लिए <math>d\ge 0</math> होता, जहाँ <math>\varphi = (1+\sqrt 5)/2 \doteq 1.618</math> होता है। (तब हमारे पास <math>n \ge F_{d+2} \ge \varphi^d</math> होता है, और log को आधार पर ले जाता है <math>\varphi</math>, <math>d\le \log_{\varphi} n</math> आवश्यकता अनुसार दोनों पक्षों का देता है।)
-ढेर में कहीं किसी भी नोड x पर विचार करें (x को मुख्य पेड़ों में से की जड़ होने की आवश्यकता नहीं है)। 'आकार'(x) को x पर जड़े पेड़ के आकार के रूप में परिभाषित करें (x के वंशजों की संख्या, जिसमें स्वयं x भी शामिल है)। हम x की ऊंचाई (x से वंशज पत्ती तक के सबसे लंबे सरल पथ की लंबाई) पर प्रेरण द्वारा साबित करते हैं कि 'आकार' (x) ≥ F<sub>d</sub><sub>+2</sub>, जहां d x की डिग्री है।
+हीप में कहीं किसी भी नोड x पर विचार करें (x को मुख्य ट्री में से की रूट होने की आवश्यकता नहीं है)। '''आकार'''(x) को x पर रूट ट्री के आकार के रूप में परिभाषित करें (x के संतति की संख्या, जिसमें स्वयं x भी सम्मिलित होता है)। हम x की ऊंचाई (x से संतति लीफ तक के सबसे लंबे सरल पथ की लंबाई) पर प्रेरण द्वारा सिद्ध करते हैं कि '''आकार''' (x) ≥ F<sub>d</sub><sub>+2</sub> होता है, जहां d x की डिग्री होती है।
-'बेस केस:' यदि x की ऊंचाई 0 है, तो d = 0, और 'आकार'(x) = 1 = F<sub>2</sub>.
+मुख्य स्थिति: यदि x की ऊंचाई 0 है, तो d = 0, और '''आकार'''(x) = 1 = F<sub>2</sub> होता है।
-आगमनात्मक मामला: मान लीजिए ''x'' की ऊंचाई सकारात्मक है और डिग्री ''d'' > 0 है। मान लीजिए ''y''<sub>1</sub>, और<sub>2</sub>, ..., और<sub>d</sub>x के बच्चे हों, उन्हें उस समय के क्रम में अनुक्रमित किया जाए जब वे हाल ही में x (y) के बच्चे बने थे<sub>1</sub> सबसे पहले और वाई होने के नाते<sub>d</sub>नवीनतम), और चलो सी<sub>1</sub>, सी<sub>2</sub>, ..., सी<sub>d</sub>उनकी संबंधित डिग्री हो. हम 'दावा' करते हैं कि सी<sub>i</sub>≥ i-2 प्रत्येक i के लिए 2 ≤ i ≤ d के साथ: y से ठीक पहले<sub>i</sub>x, y का बच्चा बना दिया गया<sub>1</sub>,...,और<sub>i</sub><sub>−1</sub> वे पहले से ही x के बच्चे थे, और इसलिए x के पास उस समय कम से कम i−1 की डिग्री थी। चूँकि वृक्षों का संयोजन तभी होता है जब उनकी जड़ों की डिग्री समान होती है, इसलिए ऐसा अवश्य हुआ होगा<sub>i</sub>जब वह x का बच्चा बना तो उसके पास कम से कम i-1 डिग्री भी थी। उस समय से लेकर आज तक, य<sub>i</sub>अधिकतम केवल बच्चा ही खोया जा सकता है (जैसा कि अंकन प्रक्रिया द्वारा गारंटी दी गई है), और इसलिए इसकी वर्तमान डिग्री सी<sub>i</sub>कम से कम i−2 है. इससे 'दावा' साबित होता है.
+प्रेरक स्थिति: मान लीजिए ''x'' की ऊंचाई धनात्मक होती है और डिग्री ''d'' > 0 है। मान लीजिए ''y''<sub>1</sub>, ''y''<sub>2</sub>, ..., ''y<sub>d</sub>'' के चाइल्ड हों, उन्हें उस समय के क्रम में अनुक्रमित किया जाता है जब वे वर्तमान में x (y) के चाइल्ड बने थे (''y''<sub>1</sub> सबसे प्रारंभिक होता है और ''y<sub>d</sub>'' नवीनतम होता है),और मान लीजिए कि ''c''<sub>1</sub>, ''c''<sub>2</sub>, ..., ''c<sub>d</sub>'' उनकी संबंधित डिग्री होती हैं। हम अनुरोध करते हैं कि 2 ≤ i ≤ d के साथ प्रत्येक i के लिए ''c<sub>i</sub>'' ≥ ''i''-2 : ''y<sub>i</sub>'' को x का चाइल्ड बनाने से ठीक पहले, ''y''<sub>1</sub>,...,''y<sub>i</sub>''<sub>−1</sub> पहले से ही x के चाइल्ड थे, और इसलिए x के पास कम से कम डिग्री थी उस समय ''i''−1थी। चूंकि ट्री तभी संयुक्त होते हैं जब उनकी रूट की डिग्री बराबर होती है, इसलिए यह अवश्य रहा होगा कि जब वह x का चाइल्ड बना तो यी के पास भी कम से कम i-1 डिग्री थी। उस समय से लेकर आज तक, ''y<sub>i</sub>'' अधिकतम मात्र चाइल्ड लुप्त हो सकता है (जैसा कि अंकन प्रक्रिया द्वारा अश्वासन दिया गया है), और इसलिए इसकी वर्तमान डिग्री ''c<sub>i</sub>'' कम से कम i−2 होती है। इससे 'वचन' सिद्ध होता है।
-चूँकि सभी y की ऊँचाइयाँ<sub>i</sub>x की तुलना में बिल्कुल कम हैं, हम 'आकार'(y) प्राप्त करने के लिए उन पर आगमनात्मक परिकल्पना लागू कर सकते हैं<sub>i</sub>) ≥एफ<sub>c<sub>i</sub></उप><sub>+2</sub>≥एफ<sub>(''i''−2)+2</sub>= एफ<sub>i</sub>. नोड्स x और y<sub>1</sub> प्रत्येक आकार(''x'') में कम से कम 1 योगदान देता है, और इसलिए हमारे पास है
+चूँकि सभी ''y<sub>i</sub>'' की ऊँचाइयाँ x की तुलना में बिल्कुल न्यूनतम होती हैं, हम 'आकार'(''y<sub>i</sub>'')≥ ''F<sub>ci</sub>''<sub>+2</sub> ≥ ''F''<sub>(''i''−2)+2</sub> = ''F<sub>i</sub>''. प्राप्त करने के लिए उन पर आगमनात्मक परिकल्पना प्रयुक्त कर सकते हैं। नोड्स x और ''y''<sub>1</sub> प्रत्येक आकार (x) में कम से कम 1 का योगदान करते हैं, और इसलिए हमारे पास है
 <math>\textbf{size}(x) \ge 2 + \sum_{i=2}^d \textbf{size}(y_i) \ge 2 + \sum_{i=2}^d F_i = 1 + \sum_{i=0}^d F_i.</math>
-नियमित प्रेरण यह साबित करता है <math>1 + \sum_{i=0}^d F_i = F_{d+2}</math> किसी के लिए <math>d\ge 0</math>, जो आकार (''x'') पर वांछित निचली सीमा देता है।
-==सबसे ख़राब मामला==
+नियमित प्रेरण यह सिद्ध करता है <math>1 + \sum_{i=0}^d F_i = F_{d+2}</math> किसी के लिए <math>d\ge 0</math> होता है, जो आकार (''x'') पर वांछित निम्नतर सीमा देता है।
-हालाँकि फाइबोनैचि ढेर बहुत कुशल दिखते हैं, उनमें निम्नलिखित दो कमियाँ हैं:<ref name=FSST>{{cite journal | last1 = Fredman | first1 = Michael L. | author1-link = Michael Fredman | last2 = Sedgewick | first2 = Robert | author2-link = Robert Sedgewick (computer scientist) | last3 = Sleator | first3 = Daniel D. | author3-link = Daniel Sleator | last4 = Tarjan | first4 = Robert E. | author4-link = Robert Tarjan | doi = 10.1007/BF01840439 | issue = 1–4 | journal = Algorithmica | pages = 111–129 | title = The pairing heap: a new form of self-adjusting heap | url = https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf | volume = 1 | year = 1986| s2cid = 23664143 }}</ref>
-# जब इन्हें लागू करने की बात आती है तो ये जटिल हो जाते हैं।
-# ढेर के सैद्धांतिक रूप से कम कुशल रूपों की तुलना में वे व्यवहार में उतने कुशल नहीं हैं। अपने सरलतम संस्करण में उन्हें प्रति नोड चार पॉइंटर्स के भंडारण और हेरफेर की आवश्यकता होती है, जबकि अन्य संरचनाओं में प्रति नोड केवल दो या तीन पॉइंटर्स की आवश्यकता होती है, जैसे कि बाइनरी हीप, बाइनोमियल हीप, [[ युग्मन ढेर |युग्मन ढेर]] , ब्रोडल कतार और रैंक पेयरिंग हीप।
-यद्यपि खाली संरचना से शुरू होने वाले संचालन के अनुक्रम का कुल चलने का समय ऊपर दी गई सीमाओं से घिरा हुआ है, अनुक्रम में कुछ (बहुत कम) संचालन को पूरा होने में बहुत लंबा समय लग सकता है (विशेष रूप से हटाएं और हटाएं में न्यूनतम रैखिक चलने का समय होता है) सबसे ख़राब मामला)। इस कारण से फाइबोनैचि ढेर और अन्य परिशोधित डेटा संरचनाएं [[वास्तविक समय कंप्यूटिंग]] | वास्तविक समय प्रणालियों के लिए उपयुक्त नहीं हो सकती हैं। ऐसी डेटा संरचना बनाना संभव है जिसका प्रदर्शन उतना ही खराब हो जितना कि फाइबोनैचि हीप का परिशोधित प्रदर्शन। ऐसी ही संरचना, ब्रोडल कतार,<ref name="bare_url">{{Citation |citeseerx=10.1.1.43.8133 |title=Worst-Case Efficient Priority Queues |year=1996 |author=Gerth Stølting Brodal |journal=Proc. 7th ACM-SIAM Symposium on Discrete Algorithms |publisher=[[Society for Industrial and Applied Mathematics]] |pages=52–58 |isbn=0-89871-366-8 |url=https://archive.org/details/proceedingsofsev0000acms/page/52 }}</ref>, रचनाकार के शब्दों में, काफी जटिल है और व्यवहार में लागू नहीं होता है। 2012 में बनाया गया, सख्त फाइबोनैचि ढेर रेफरी><nowiki></ref></nowiki> समान सबसे खराब स्थिति वाली सरल (ब्रोडल की तुलना में) संरचना है। सरल संरचना होने के बावजूद, प्रयोगों से पता चलता है कि व्यवहार में सख्त फाइबोनैचि ढेर अधिक जटिल ब्रोडल कतार की तुलना में धीमा प्रदर्शन करता है और बुनियादी फाइबोनैचि ढेर की तुलना में भी धीमा है। रेफरी>X<nowiki></ref></nowiki><ref name=":0" />ड्रिस्कॉल एट अल के रन-रिलैक्स्ड ढेर। मर्ज को छोड़कर सभी फाइबोनैचि हीप संचालन के लिए सबसे खराब स्थिति में अच्छा प्रदर्शन दें।
+==सबसे व्यर्थ स्थिति  ==
+यघपि फाइबोनैचि हीप बहुत कुशल दिखते हैं, उनमें निम्नलिखित दो कमियाँ होती हैं:<ref name="FSST">{{cite journal | last1 = Fredman | first1 = Michael L. | author1-link = Michael Fredman | last2 = Sedgewick | first2 = Robert | author2-link = Robert Sedgewick (computer scientist) | last3 = Sleator | first3 = Daniel D. | author3-link = Daniel Sleator | last4 = Tarjan | first4 = Robert E. | author4-link = Robert Tarjan | doi = 10.1007/BF01840439 | issue = 1–4 | journal = Algorithmica | pages = 111–129 | title = The pairing heap: a new form of self-adjusting heap | url = https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf | volume = 1 | year = 1986| s2cid = 23664143 }}</ref>
+# जब इन्हें प्रयुक्त करने की बात आती है तो ये सम्मिश्र हो जाते हैं।
+# हीप के सैद्धांतिक रूप से कम कुशल रूपों की तुलना में वे व्यवहार में उतने कुशल नहीं होते हैं। अपने सरलतम संस्करण में उन्हें प्रति नोड चार संकेत के संग्रह और संचालन की आवश्यकता होती है, जबकि अन्य संरचनाओं में प्रति नोड मात्र दो या तीन संकेतकी आवश्यकता होती है, जैसे कि बाइनरी हीप, बाइनोमियल हीप, [[ युग्मन ढेर |युग्मन हीप]], ब्रोडल पंक्ति और रैंक पेयरिंग हीप।
+यद्यपि रिक्त संरचना से प्रारम्भ होने वाले संचालन के अनुक्रम का कुल चलने का समय ऊपर दी गई सीमाओं से घिरा हुआ होता है, अनुक्रम में कुछ (बहुत कम) संचालन को पूरा होने में बहुत लंबा समय लग सकता है (विशेष रूप से हटाएं और हटाएं में न्यूनतम रैखिक चलने का समय सबसे व्यर्थ स्थिति में होता है)। इस कारण से फाइबोनैचि हीप और अन्य परिशोधित डेटा संरचनाएं [[वास्तविक समय कंप्यूटिंग]] के लिए उपयुक्त नहीं हो सकती हैं। ऐसी डेटा संरचना बनाना संभव है जिसका प्रदर्शन उतना ही व्यर्थ हो जितना कि फाइबोनैचि हीप का परिशोधित प्रदर्शन करना होता है। ऐसी ही संरचना, ब्रोडल पंक्ति ,<ref name="bare_url">{{Citation |citeseerx=10.1.1.43.8133 |title=Worst-Case Efficient Priority Queues |year=1996 |author=Gerth Stølting Brodal |journal=Proc. 7th ACM-SIAM Symposium on Discrete Algorithms |publisher=[[Society for Industrial and Applied Mathematics]] |pages=52–58 |isbn=0-89871-366-8 |url=https://archive.org/details/proceedingsofsev0000acms/page/52 }}</ref>, रचनाकार के शब्दों में, अधिक सम्मिश्र होती है और व्यवहार में प्रयुक्त नहीं होती है। 2012 में बनाया गया, कठोर फाइबोनैचि हीप रेफरी समान सबसे व्यर्थ स्थिति वाली सरल (ब्रोडल की तुलना में) संरचना होती है। सरल संरचना होने के पश्चात् भी, प्रयोगों से पता चलता है कि व्यवहार में कठोर फाइबोनैचि हीप अधिक सम्मिश्र ब्रोडल पंक्ति की तुलना में धीमा प्रदर्शन करता है और बुनियादी फाइबोनैचि हीप की तुलना में भी धीमा होता है।<ref name=":0" />ड्रिस्कॉल एट अल के रन-शिथिलीकृत हीप विलय को छोड़कर सभी फाइबोनैचि हीप संचालन के लिए सबसे खराब स्थिति में अच्छा प्रदर्शन करते है।
 ==चलने के समय का सारांश==
@@ Line 90: / Line 90: @@
 ==व्यावहारिक विचार==
-फाइबोनैचि हीप्स को व्यवहार में धीमे होने के लिए जाना जाता है<ref>http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/FibonacciHeaps.pdf, p. 79</ref> प्रति नोड बड़ी मेमोरी खपत और सभी परिचालनों पर उच्च स्थिर कारकों के कारण। हाल के प्रयोगात्मक परिणामों से पता चलता है कि फाइबोनैचि ढेर अपने अधिकांश बाद के डेरिवेटिव की तुलना में व्यवहार में अधिक कुशल हैं, जिनमें भूकंप ढेर, उल्लंघन ढेर, सख्त फाइबोनैचि ढेर, रैंक पेयरिंग ढेर शामिल हैं, लेकिन युग्मन ढेर या सरणी-आधारित ढेर की तुलना में कम कुशल हैं।<ref name=":0">{{cite journal|last1=Larkin|first1=Daniel|last2=Sen|first2=Siddhartha|last3=Tarjan|first3=Robert|title=प्राथमिकता कतारों का एक बैक-टू-बेसिक्स अनुभवजन्य अध्ययन|journal=Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments|date=2014|pages=61–72|doi=10.1137/1.9781611973198.7|arxiv=1403.0252|bibcode=2014arXiv1403.0252L|isbn=978-1-61197-319-8|s2cid=15216766}}</ref>
+प्रति नोड बड़ी संग्रह उपभोग और सभी परिचालनों पर उच्च स्थिर कारकों के कारण फाइबोनैचि हीप्स को व्यवहार में मंद होने के लिए जाना जाता है<ref>http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/FibonacciHeaps.pdf, p. 79</ref>। वर्तमान के प्रयोगात्मक परिणामों से पता चलता है कि फाइबोनैचि हीप अपने अधिकांश पश्चात् के संजात की तुलना में व्यवहार में अधिक कुशल होते हैं, जिनमें भूकंप हीप, उल्लंघन हीप, सख्त फाइबोनैचि हीप, रैंक पेयरिंग हीप सम्मिलित होते हैं, यघपि युग्मन हीप या सरणी-आधारित हीप की तुलना में निम्न कुशल होते हैं।<ref name=":0">{{cite journal|last1=Larkin|first1=Daniel|last2=Sen|first2=Siddhartha|last3=Tarjan|first3=Robert|title=प्राथमिकता कतारों का एक बैक-टू-बेसिक्स अनुभवजन्य अध्ययन|journal=Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments|date=2014|pages=61–72|doi=10.1137/1.9781611973198.7|arxiv=1403.0252|bibcode=2014arXiv1403.0252L|isbn=978-1-61197-319-8|s2cid=15216766}}</ref>
 == संदर्भ ==
@@ Line 106: / Line 106: @@
 {{Data structures}}
-{{DEFAULTSORT:Fibonacci Heap}}[[Category: फाइबोनैचि संख्याएँ]] [[Category: ढेर (डेटा संरचनाएं)]] [[Category: परिशोधित डेटा संरचनाएँ]]
+{{DEFAULTSORT:Fibonacci Heap}}
-[[Category: Machine Translated Page]]
+[[Category:CS1 English-language sources (en)]]
-[[Category:Created On 07/07/2023]]
+[[Category:Collapse templates|Fibonacci Heap]]
+[[Category:Created On 07/07/2023|Fibonacci Heap]]
+[[Category:Lua-based templates|Fibonacci Heap]]
+[[Category:Machine Translated Page|Fibonacci Heap]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists|Fibonacci Heap]]
+[[Category:Pages with script errors|Fibonacci Heap]]
+[[Category:Sidebars with styles needing conversion|Fibonacci Heap]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready|Fibonacci Heap]]
+[[Category:Templates generating microformats|Fibonacci Heap]]
+[[Category:Templates that add a tracking category|Fibonacci Heap]]
+[[Category:Templates that are not mobile friendly|Fibonacci Heap]]
+[[Category:Templates that generate short descriptions|Fibonacci Heap]]
+[[Category:Templates using TemplateData|Fibonacci Heap]]
+[[Category:Wikipedia metatemplates|Fibonacci Heap]]
+[[Category:ढेर (डेटा संरचनाएं)|Fibonacci Heap]]
+[[Category:परिशोधित डेटा संरचनाएँ|Fibonacci Heap]]
+[[Category:फाइबोनैचि संख्याएँ|Fibonacci Heap]]

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

Anonymous

Search

फाइबोनैचि हीप: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 19:27, 21 July 2023

Contents

संरचना

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

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

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

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

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

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

फाइबोनैचि हीप: Difference between revisions

Latest revision as of 19:27, 21 July 2023

संरचना

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

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

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

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

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

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories