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