data structures - करण - फाइबोनैकी ढेर डेटा संरचना के पीछे अंतर्ज्ञान क्या है?



हिंदी में डेटा संरचना के वर्गीकरण (1)

मैंने फिबोनाची ढेर पर विकिपीडिया लेख पढ़ा है और डेटा संरचना के सीएलआरएस के विवरण को पढ़ा है, लेकिन वे इस डेटा संरचना के काम के लिए थोड़ा अंतर्ज्ञान प्रदान करते हैं। फाइबोनैकी ढेर क्यों तरीके से डिजाइन किए गए हैं? वो कैसे काम करते है?

धन्यवाद!


यह जवाब काफी लंबा होने जा रहा है, लेकिन मुझे आशा है कि यह कुछ अंतर्दृष्टि प्रदान करने में मदद करेगी कि फिबोनाची ढेर कहां से आता है। मैं यह मानने जा रहा हूं कि आप पहले से ही द्विपक्षीय ढेर और अमूर्त विश्लेषण से परिचित हैं।

प्रेरणा: क्यों Fibonacci ढेर?

फिबोनाची ढेर में कूदने से पहले, यह पता लगाना शायद अच्छा है कि हमें उन्हें पहले स्थान की आवश्यकता क्यों है। अन्य प्रकार के ढेर हैं ( बाइनरी ढेर और द्विपदीय ढेर , उदाहरण के लिए), तो हमें किसी और की आवश्यकता क्यों है?

मुख्य कारण डिजस्ट्रा के एल्गोरिदम और प्राइम के एल्गोरिदम में आता है । इन दोनों ग्राफ एल्गोरिदम संबंधित प्राथमिकताओं के साथ प्राथमिकता कतार होल्डिंग नोड्स को बनाए रखकर काम करते हैं। दिलचस्प बात यह है कि ये एल्गोरिदम एक हीप ऑपरेशन पर भरोसा करते हैं जिसे कमी-कुंजी कहा जाता है जो पहले से ही प्राथमिकता कतार में प्रवेश लेता है और फिर इसकी कुंजी कम करता है (यानी इसकी प्राथमिकता बढ़ जाती है)। वास्तव में, इन एल्गोरिदम के बहुत से रनटाइम को आपको कम-कुंजी कॉल करने की संख्या से समझाया जाता है। यदि हम एक डेटा संरचना बना सकते हैं जो कमी-कुंजी को अनुकूलित करता है, तो हम इन एल्गोरिदम के प्रदर्शन को अनुकूलित कर सकते हैं। बाइनरी ढेर और द्विपदीय ढेर के मामले में, कमी-कुंजी में समय लगता है ओ (लॉग एन), जहां एन प्राथमिकता कतार में नोड्स की संख्या है। अगर हम इसे ओ (1) में छोड़ सकते हैं, तो डिजस्ट्रा के एल्गोरिदम और प्राइम के एल्गोरिदम की समय जटिलताओं ओ (एम लॉग एन) से (एम + एन लॉग एन) से गिर जाएगी, जो पहले की तुलना में असंवेदनशील रूप से तेज है। इसलिए, डेटा संरचना बनाने की कोशिश करना समझ में आता है जो कम-कुंजी को कुशलता से समर्थन देता है।

बेहतर ढेर संरचना को डिजाइन करने पर विचार करने का एक और कारण है। एक खाली बाइनरी ढेर में तत्व जोड़ते समय, प्रत्येक प्रविष्टि में समय ओ (लॉग एन) लगता है। ओ (एन) में बाइनरी ढेर बनाना संभव है यदि हम सभी एन तत्वों को पहले से जानते हैं, लेकिन यदि तत्व स्ट्रीम में आते हैं तो यह संभव नहीं है। द्विपक्षीय ढेर के मामले में, लगातार तत्वों को सम्मिलित करने से एओ (1) प्रत्येक को अमूर्त समय लगता है, लेकिन यदि सम्मिलन विलोपन के साथ अंतःस्थापित होते हैं, तो प्रविष्टियां प्रत्येक Ω (लॉग एन) समय ले सकती हैं। इसलिए, हम प्राथमिकता कतार कार्यान्वयन की खोज करना चाहेंगे जो प्रत्येक समय (1) समय लेने के लिए सम्मिलन को अनुकूलित करता है।

चरण एक: आलसी द्विपदीय ढेर

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

यदि आपको याद होगा, द्विपक्षीय ढेर द्विपदीय पेड़ के संग्रह में ढेर में सभी तत्वों को संग्रहीत करके काम करते हैं । ऑर्डर एन के एक द्विपदीय पेड़ में 2 एन नोड्स हैं, और ढेर बिनोमियल पेड़ों के संग्रह के रूप में संरचनाएं हैं जो सभी ढेर संपत्ति का पालन करते हैं। आम तौर पर, एक द्विपक्षीय ढेर में सम्मिलन एल्गोरिदम निम्नानुसार कार्य करता है:

  • एक नया सिंगलटन नोड बनाएं (यह ऑर्डर 0 का पेड़ है)।
  • यदि आदेश 0 का पेड़ है:
    • ऑर्डर के दो पेड़ों को एक साथ क्रमशः 1 के पेड़ में मिलाएं।
    • यदि आदेश 1 का पेड़ है:
      • आदेश 1 के दो पेड़ों को एक पेड़ आदेश 2 में मिलाएं।
      • यदि आदेश 2 का पेड़ है:
      • ...

यह प्रक्रिया सुनिश्चित करती है कि प्रत्येक बिंदु पर, प्रत्येक आदेश के अधिकांश पेड़ पर होता है। चूंकि प्रत्येक पेड़ अपने आदेश की तुलना में तेजी से अधिक नोड्स रखता है, यह गारंटी देता है कि पेड़ों की कुल संख्या छोटी है, जो डेक्यू को जल्दी से चलाने देती है (क्योंकि हमें डेक्यू-मिनट कदम करने के बाद बहुत से अलग पेड़ों को देखने की ज़रूरत नहीं है)।

हालांकि, इसका यह भी अर्थ है कि एक द्विपदीय ढेर में नोड डालने का सबसे खराब मामला रनटाइम Θ (लॉग एन) है, क्योंकि हमारे पास Θ (लॉग n) पेड़ हो सकते हैं जिन्हें एक साथ विलय करने की आवश्यकता होती है। उन पेड़ों को केवल एक साथ विलय करने की आवश्यकता है क्योंकि हमें डेक्यू कदम करते समय पेड़ों की संख्या कम रखने की आवश्यकता होती है, और पेड़ों की संख्या को कम रखने के लिए भविष्य में सम्मिलन में बिल्कुल कोई फायदा नहीं होता है।

यह द्विपक्षीय ढेर से पहला प्रस्थान प्रस्तुत करता है:

संशोधन 1 : ढेर में नोड डालने पर, बस ऑर्डर 0 का पेड़ बनाएं और इसे पेड़ के मौजूदा संग्रह में जोड़ें। पेड़ों को एक साथ समेकित न करें।

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

संशोधन 2 : दो ढेर एक साथ विलय करते समय, बस अपने सभी पेड़ों को बिना किसी विलय के गठबंधन करें। किसी भी पेड़ को एक साथ समेकित न करें।

यदि हम यह परिवर्तन करते हैं, तो हम अपने एनक्यू ऑपरेशंस पर ओ (1) प्रदर्शन को आसानी से प्राप्त करते हैं, क्योंकि हम जो भी कर रहे हैं वह एक नया नोड बना रहा है और इसे पेड़ों के संग्रह में जोड़ रहा है। हालांकि, अगर हम सिर्फ यह परिवर्तन करते हैं और कुछ भी नहीं करते हैं, तो हम पूरी तरह से डेक्यू-मिन ऑपरेशन के प्रदर्शन को तोड़ देते हैं। याद रखें कि न्यूनतम मूल्य को हटाने के बाद ढेर में सभी पेड़ों की जड़ों में डिक्यू-मिनट को स्कैन करने की आवश्यकता है ताकि इसे सबसे छोटा मूल्य मिल सके। यदि हम उन्हें रास्ते में डालने से Θ (एन) नोड्स में जोड़ते हैं, तो हमारे डेक्यू ऑपरेशन को इन सभी पेड़ों को देखकर Θ (एन) समय व्यतीत करना होगा। यह एक बड़ा प्रदर्शन हिट है ... क्या हम इससे बच सकते हैं?

यदि हमारे सम्मिलन वास्तव में केवल अधिक पेड़ जोड़ते हैं, तो हम पहले डेक्यू निश्चित रूप से Ω (एन) समय ले लेंगे। हालांकि, इसका मतलब यह नहीं है कि हर डेक्यू महंगा होना चाहिए। क्या होता है, अगर एक डेक्यू करने के बाद, हम ढेर में सभी पेड़ों को एक साथ जोड़ते हैं जैसे कि हम प्रत्येक आदेश के केवल एक पेड़ के साथ खत्म होते हैं? शुरुआत में इसमें काफी समय लगेगा, लेकिन यदि हम उत्तराधिकार में कई डेक्यू करना शुरू करते हैं, तो भविष्य के डेक्यू काफी तेजी से होंगे क्योंकि कम पेड़ झूठ बोल रहे हैं।

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

इस एल्गोरिदम के पीछे अंतर्ज्ञान निम्नलिखित है। मान लीजिए कि हम एक हैश टेबल बनाते हैं जो पेड़ के आदेश से पेड़ों तक नक्शा बनाता है। हम डेटा संरचना में प्रत्येक पेड़ के लिए निम्नलिखित ऑपरेशन कर सकते हैं:

  • देखो और देखें कि क्या पहले से ही उस आदेश का पेड़ है।
  • यदि नहीं, तो वर्तमान पेड़ हैश तालिका में डालें।
  • अन्यथा:
    • उस पेड़ के पेड़ के साथ वर्तमान पेड़ को मर्ज करें, हैश टेबल से पुराने पेड़ को हटा दें।
    • इस प्रक्रिया को दोबारा दोहराएं।

यह ऑपरेशन सुनिश्चित करता है कि जब हम पूरा कर लेंगे, तो प्रत्येक आदेश के अधिकांश पेड़ पर होगा। यह भी अपेक्षाकृत कुशल है। मान लीजिए कि हम कुल पेड़ों के साथ शुरू करते हैं और कुल पेड़ों के साथ खत्म होते हैं। कुल विलय की संख्या हम कर देंगे, टी-टी -1 होगा, और हर बार जब हम विलय करते हैं तो इसमें समय (1) करने में समय लगेगा। इसलिए, इस ऑपरेशन के लिए रनटाइम पेड़ों की संख्या में रैखिक होगा (प्रत्येक पेड़ कम से कम एक बार देखा जाता है) साथ ही विलय की संख्या भी होती है।

यदि पेड़ की संख्या छोटी है (कहें, Θ (लॉग एन)), तो इस ऑपरेशन में केवल समय ओ (लॉग एन) लगेगा। यदि पेड़ की संख्या बड़ी है (कहें, Θ (एन)), तो यह ऑपरेशन Θ (एन) समय लेगा, लेकिन केवल शेष Θ (लॉग एन) पेड़ छोड़ देगा, भविष्य में डेक्यूज को तेजी से हटा देगा।

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

  • सम्मिलित करें : क्या ओ (1) काम करता है और एक से क्षमता बढ़ाता है। अमूर्त लागत ओ (1) है।
  • मर्ज करें : क्या ओ (1) काम करता है। एक ढेर की क्षमता 0 तक गिर जाती है और अन्य ढेर की क्षमता इसी राशि से बढ़ जाती है, इसलिए संभावित में कोई शुद्ध परिवर्तन नहीं होता है। अमूर्त लागत इस प्रकार ओ (1) है।
  • Dequeue-Min : क्या ओ (#trees + #merges) काम करता है और संभावित रूप से Θ (लॉग एन) तक कम हो जाता है, यदि हम उत्सुकता से वृक्षों को विलय कर रहे थे तो हम द्विपदीय पेड़ में पेड़ों की संख्या लेंगे। हम इसके लिए एक अलग तरीके से खाते हैं। आइए पेड़ों की संख्या Θ (लॉग एन) + ई के रूप में लिखी जाए, जहां ई पेड़ों की "अतिरिक्त" संख्या है। उस स्थिति में, कुल कार्य किया जाता है Θ (लॉग एन + ई + # विर्ज)। ध्यान दें कि हम प्रति अतिरिक्त पेड़ में एक विलय करेंगे, और इसलिए कुल कार्य Θ (लॉग एन + ई) है। चूंकि हमारी क्षमता Θ (लॉग एन) + ई से नीचे Θ (लॉग एन) से पेड़ों की संख्या को छोड़ देती है, संभावित रूप से ड्रॉप -ई है। इसलिए, एक डेक्यू-मिनट की अमूर्त लागत Θ (लॉग एन) है।

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

इसलिए:

संशोधन 3 : एक डेक्यू-मिन ऑपरेशन पर, सभी पेड़ों को समेकित करने के लिए प्रत्येक आदेश के अधिकांश पेड़ पर सुनिश्चित करें।

इस बिंदु पर, हमने समय ओ (1) में चलने और विलय करने के लिए आवंटित समय ओ (लॉग एन) में चल रहे डेक्यू को डाला है। वह बहुत निफ्टी है! हालांकि, अभी भी हमारे पास अभी भी कमी-कुंजी काम नहीं है। यह चुनौतीपूर्ण हिस्सा होगा।

चरण दो: कमी-कुंजी लागू करना

फिलहाल, हमारे पास फिबोनाची ढेर के बजाय "आलसी द्विपदीय ढेर" है। एक द्विपक्षीय ढेर और फिबोनाची ढेर के बीच वास्तविक परिवर्तन यह है कि हम कैसे कमी-कुंजी को कार्यान्वित करते हैं।

याद रखें कि कमी-कुंजी ऑपरेशन को ढेर में पहले से ही एक प्रविष्टि लेनी चाहिए (आमतौर पर, हमारे पास एक सूचक होता है) और एक नई प्राथमिकता जो मौजूदा प्राथमिकता से कम है। इसके बाद वह उस तत्व की प्राथमिकता को नई, निचली प्राथमिकता में बदल देता है।

हम इस ऑपरेशन को बहुत तेज़ी से कार्यान्वित कर सकते हैं (समय ओ (लॉग एन) में) एक सीधा एल्गोरिदम का उपयोग कर। उस तत्व को लें जिसकी कुंजी कम होनी चाहिए (जो ओ (1) समय में स्थित हो सकती है; याद रखें, हम मानते हैं कि हमारे पास एक सूचक है) और इसकी प्राथमिकता कम करें। फिर, इसे अपने माता-पिता नोड के साथ बार-बार स्वैप करें जब तक कि इसकी प्राथमिकता उसके माता-पिता से कम न हो, नोड को आराम करने पर या पेड़ की जड़ तक पहुंचने पर रोक दें। इस ऑपरेशन में समय ओ (लॉग एन) लगता है क्योंकि प्रत्येक पेड़ की ऊंचाई ओ (लॉग एन) पर होती है और प्रत्येक तुलना में समय ओ (1) लगता है।

याद रखें, हालांकि, हम इससे भी बेहतर करने की कोशिश कर रहे हैं - हम रनटाइम ओ (1) होना चाहते हैं! यह मैच के लिए एक बहुत मुश्किल है। हम किसी भी प्रक्रिया का उपयोग नहीं कर सकते जो नोड को पेड़ को ऊपर या नीचे ले जायेगा, क्योंकि उन पेड़ों की ऊँचाई होती है जो Ω (लॉग एन) हो सकती हैं। हमें कुछ और कठोर कोशिश करनी होगी।

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

संशोधन 4 : कमी-कुंजी नोड की कुंजी को कम करें और, यदि इसकी प्राथमिकता अपने माता-पिता की प्राथमिकता से छोटी है, तो इसे काटकर रूट सूची में जोड़ें।

इस ऑपरेशन का असर क्या होगा? कई चीजें घटित होंगी।

  1. नोड जो पहले हमारे बच्चे के रूप में हमारे नोड था, अब सोचता है कि इसमें बच्चों की गलत संख्या है। याद रखें कि आदेश एन का एक द्विपक्षीय पेड़ एन बच्चों के लिए परिभाषित किया गया है, लेकिन यह अब और सत्य नहीं है।
  2. जड़ सूची में पेड़ों का संग्रह बढ़ जाएगा, भविष्य में डेक्यू संचालन की लागत में वृद्धि होगी।
  3. हमारे ढेर में पेड़ जरूरी नहीं कि वे द्विपदीय पेड़ बन जाएंगे। वे "पूर्व में" द्विपदीय पेड़ हो सकते हैं जो समय पर विभिन्न बिंदुओं पर बच्चों को खो देते हैं।

संख्या (1) एक समस्या का बहुत अधिक नहीं है। अगर हम अपने माता-पिता से नोड काटते हैं, तो हम उस नोड के आदेश को केवल एक से कम कर सकते हैं ताकि यह इंगित किया जा सके कि इसमें कम बच्चे हैं जो पहले सोचा था। संख्या (2) भी एक समस्या नहीं है। हम कमी-कुंजी ऑपरेशन के लिए अगले डेक्यू-मिन ऑपरेशन में किए गए अतिरिक्त काम को केवल बैकचार्ज कर सकते हैं।

संख्या (3) एक बहुत ही गंभीर समस्या है जिसे हमें संबोधित करने की आवश्यकता होगी। यहां समस्या है: एक द्विपक्षीय ढेर की दक्षता आंशिक रूप से इस तथ्य से उपजी है कि एन नोड्स का कोई भी संग्रह विभिन्न आदेशों के Θ (लॉग एन) पेड़ों के संग्रह में संग्रहीत किया जा सकता है। इसका कारण यह है कि प्रत्येक द्विपक्षीय पेड़ में 2 एन नोड्स होते हैं। अगर हम पेड़ से नोड्स काटने शुरू कर सकते हैं, तो हम उन पेड़ों को खतरे में डाल सकते हैं जिनमें बड़ी संख्या में बच्चे हैं (यानी, एक उच्च आदेश) लेकिन जिनके पास कई नोड्स नहीं हैं। उदाहरण के लिए, मान लें कि हम ऑर्डर के एक पेड़ से शुरू करते हैं और फिर के सभी पोते-पोतों पर कमी-कुंजी संचालन करते हैं। यह के पे के रूप में के पेड़ के रूप में छोड़ देता है, लेकिन जिसमें केवल के + 1 कुल नोड्स होते हैं। अगर हम हर जगह इस प्रक्रिया को दोहराते रहते हैं, तो हम विभिन्न आदेशों के पेड़ों के गुच्छा के साथ समाप्त हो सकते हैं जिनमें उनमें बहुत कम संख्या में बच्चे हैं। नतीजतन, जब हम पेड़ों को एक साथ समूहबद्ध करने के लिए हमारे सहस्राब्दी ऑपरेशन करते हैं, तो हम पेड़ों की संख्या को प्रबंधनीय स्तर पर कम नहीं कर सकते हैं, Θ (लॉग एन) को तोड़ने के लिए बाध्य हो सकते हैं, जिसे हम वास्तव में खोना नहीं चाहते हैं।

इस बिंदु पर, हम एक बांध में हैं। हमें पेड़ों को फिर से बदलने के तरीके के साथ बहुत लचीलापन की आवश्यकता है ताकि हम ओ (1) समय कम करने की कुंजी कार्यक्षमता प्राप्त कर सकें, लेकिन हम पेड़ों को मनमाने ढंग से दोबारा नहीं दे सकते हैं या हम कमी के साथ समाप्त हो जाएंगे- कुंजी का amortized रनटाइम ओ से अधिक कुछ (लॉग एन) में बढ़ रहा है।

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

यह पता चला है कि यह एक महान समझौता है। यह हमें अधिकांश संदर्भों में जल्दी से कम-चाबियाँ करने देता है (जब तक नोड्स एक ही पेड़ के बच्चे नहीं होते हैं), और केवल दुर्लभ रूप से हमें अपने माता-पिता से नोड काटकर कमी-कुंजी "प्रसारित करना" होता है और फिर अपने दादा से उस नोड काटने।

ट्रैक करने के लिए कि कौन से नोड्स ने बच्चों को खो दिया है, हम प्रत्येक नोड को "मार्क" बिट असाइन करेंगे। प्रत्येक नोड प्रारंभ में मार्क बिट साफ़ हो जाएगा, लेकिन जब भी यह एक बच्चे को खो देता है तो यह थोड़ा सेट होगा। यदि बिट पहले से सेट हो जाने के बाद दूसरा बच्चा खो देता है, तो हम थोड़ा साफ़ कर देंगे, फिर नोड को अपने माता-पिता से काट लेंगे।

संशोधन 5 : प्रारंभिक रूप से झूठी प्रत्येक नोड को एक मार्क बिट असाइन करें। जब एक बच्चे को एक अनचाहे माता-पिता से काट दिया जाता है, तो माता-पिता को चिह्नित करें। जब किसी बच्चे को चिह्नित अभिभावक से काट दिया जाता है, तो माता-पिता को अनमार्क करें और माता-पिता को अपने माता-पिता से काट दें।

इस पुराने स्टैक ओवरफ्लो प्रश्न में , मैंने एक सबूत तैयार किया है जो दिखाता है कि यदि पेड़ों को इस तरह से संशोधित करने की अनुमति है, तो आदेश एन के किसी भी पेड़ में कम से कम Θ (φ n ) नोड्स होना चाहिए, जहां φ सुनहरा है अनुपात , लगभग 1.61। इसका मतलब है कि पेड़ के क्रम में प्रत्येक पेड़ में नोड्स की संख्या अभी भी घातीय है, हालांकि यह पहले से कम एक्सपोनेंट है। नतीजतन, विश्लेषण जो हमने कमी-कुंजी ऑपरेशन की जटिलता के बारे में पहले किया था, अभी भी है, हालांकि Θ (लॉग एन) बिट में छिपा शब्द अलग होगा।

विचार करने के लिए एक बहुत ही आखिरी बात है - कमी की कुंजी की जटिलता के बारे में क्या? पहले, यह ओ (1) था क्योंकि हम उचित नोड पर जड़ वाले पेड़ को काटते हैं और इसे रूट सूची में ले जाते हैं। हालांकि, अब हमें "कैस्केडिंग कट" करना पड़ सकता है, जिसमें हमने अपने माता-पिता से नोड काट दिया है, फिर उस नोड को अपने माता-पिता से काट दें। यह ओ (1) समय कम करने वाली चाबियाँ कैसे देता है?

यहां पर अवलोकन यह है कि हम प्रत्येक कमी-कुंजी ऑपरेशन के लिए "चार्ज" जोड़ सकते हैं जिसे हम अपने माता-पिता से पैरेंट नोड को काटने के लिए खर्च कर सकते हैं। चूंकि हम अपने माता-पिता से केवल एक नोड काटते हैं, यदि यह पहले से ही दो बच्चों को खो देता है, तो हम दिखा सकते हैं कि प्रत्येक कमी-कुंजी ऑपरेशन अपने मूल नोड को काटने के लिए आवश्यक काम के लिए भुगतान करता है। जब हम माता-पिता को काटते हैं, तो हम पहले की कमी-कुंजी संचालन में से किसी एक को वापस करने की लागत का शुल्क ले सकते हैं। नतीजतन, भले ही किसी भी व्यक्तिगत कमी-कुंजी ऑपरेशन को समाप्त करने में काफी समय लग सकता है, फिर भी हम पहले की कॉल में काम को हमेशा मिश्रित कर सकते हैं ताकि रनटाइम ओ (1) को अमूर्त किया जा सके।

चरण तीन: लिंक्ड सूचियां बहुत अधिक हैं!

एक अंतिम विवरण है जिसके बारे में हमें बात करनी है। अब तक वर्णित डेटा संरचना मुश्किल है, लेकिन यह आपदाजनक रूप से जटिल नहीं लगती है। Fibonacci ढेर भयभीत होने के लिए एक प्रतिष्ठा है ... वह क्यों है?

इसका कारण यह है कि ऊपर वर्णित सभी परिचालनों को लागू करने के लिए, पेड़ संरचनाओं को बहुत चालाक तरीकों से लागू करने की आवश्यकता है।

आम तौर पर, आप प्रत्येक माता-पिता को सभी बच्चों (शायद बच्चों की सरणी करके ) या बाएं-बच्चे / दाएं-भाई के प्रतिनिधित्व का उपयोग करके एक मल्टीवे पेड़ का प्रतिनिधित्व करेंगे , जहां माता-पिता के पास एक पॉइंटर होता है बच्चा, जो बदले में अन्य बच्चों की एक सूची को इंगित करता है। एक द्विपदीय ढेर के लिए, यह सही है। वृक्षों पर हमें जो मुख्य ऑपरेशन करने की ज़रूरत है वह एक जुड़ाव ऑपरेशन है जिसमें हम एक रूट नोड को दूसरे के बच्चे बनाते हैं, इसलिए माता-पिता से बच्चों के लिए निर्देशित पेड़ में पॉइंटर्स के लिए यह बिल्कुल उचित है।

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

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

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

  • एक पेड़ को दूसरे के बच्चे बनाओ: यदि पहले पेड़ में कोई बच्चा नहीं है, तो अपने बच्चे के सूचक को दूसरे पेड़ पर इंगित करने के लिए सेट करें। अन्यथा, दूसरे पेड़ को पहले पेड़ की गोलाकार रूप से जुड़ी बाल सूची में विभाजित करें।

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

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

संशोधन 6 : पेड़ के एक कस्टम प्रतिनिधित्व का प्रयोग करें जो पेड़ के कुशल जुड़ने और दूसरे से एक पेड़ काटने का समर्थन करता है।

निष्कर्ष

मुझे आशा है कि यह जवाब रहस्य पर कुछ प्रकाश डालेगा जो कि फिबोनाची ढेर है। मुझे आशा है कि आप उचित अंतर्दृष्टि के आधार पर सरल चरणों की एक श्रृंखला द्वारा एक जटिल संरचना (द्विपक्षीय ढेर) से तार्किक प्रगति को और अधिक जटिल संरचना में देख सकते हैं। विलोपन की कीमत पर सम्मिलन को कुशल बनाना चाहते हैं, और यह समान रूप से subtrees को काटकर कमी-कुंजी को लागू करने के लिए बहुत पागल नहीं है। वहां से, शेष विवरण यह सुनिश्चित करने में हैं कि संरचना अभी भी कुशल है, लेकिन वे कारणों के बजाय अन्य भागों के अधिक परिणाम हैं।

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

उम्मीद है की यह मदद करेगा!





fibonacci-heap