डी-एरी हीप

d-एरी हीप या d-हीप एक प्राथमिक डेटा संरचना होती है, जो बाइनरी हीप का एक सामान्यीकरण होता है जिसमें नोड्स होते है d 2। इस प्रकार, एक बाइनरी हीप 2-हीप होती है, और एक टर्नरी हीप 3-हीप होती है। टारजन और जेन्सेन एट अल के अनुसार d-एरी हीप्स का आविष्कार डोनाल्ड बी. जॉनसन ने 1975 में किया था।

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

डेटा संरचना

d-एरी हीप में एक ऐरे डेटा संरचना होती है n, जिनमें से प्रत्येक के साथ एक प्राथमिकता जुड़ी हुई होती है। इन वस्तुओं को संपूर्ण रूप से नोड्स के रूप में देखा जा सकता है d-एरी ट्री,: सरणी की स्थिति 0 पर (शून्य-आधारित नंबरिंग का उपयोग करके) ट्री बनाता है, स्थिति 1 से लेकर d तक इसके चाइल्ड नोड होते है इस प्रकार, स्थिति में वस्तु का जनक i (किसी के लिए i > 0) स्थिति पर वस्तु है ⌊(i − 1)/d⌋ और उसके चाइल्ड पदों पर वस्तु है di + 1 द्वारा di + d. बाइनरी हीप के अनुसार, मिन-हीप में, प्रत्येक वस्तु की एक प्राथमिकता होती है जो कम से कम उसके मूल के बराबर बड़ी होती है; अधिकतम-हीप में, प्रत्येक वस्तु की एक प्राथमिकता होती है जो उसके मूल से बड़ी नहीं होती है।

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

हीप में एक नया वस्तु डालने के लिए, वस्तु को सरणी के अंत में जोड़ा जाता है, और फिर जब हीप संपत्ति का उल्लंघन होता है तो इसे अपने मूल के साथ बदल दिया जाता है, इसे पेड़ में ऊपर की ओर और सरणी में पहले ले जाया जाता है, जब तक कि अंततः हीप संपत्ति संतुष्ट है. उसी अपवर्ड-स्वैपिंग प्रक्रिया का उपयोग न्यूनतम-हीप में किसी वस्तु की प्राथमिकता को कम करने, या अधिकतम-हीप में किसी वस्तु की प्राथमिकता को बढ़ाने के लिए किया जा सकता है।

किसी सारणी से एक नया हीप बनाने के लिए n वस्तु, कोई वस्तु की स्थिति से शुरू करते हुए, रिवर्स ऑर्डर में वस्तु पर लूप कर सकता है n − 1 और वस्तु को स्थिति 0 पर समाप्त करते हुए, प्रत्येक वस्तु के लिए डाउनवर्ड-स्वैपिंग प्रक्रिया को लागू करना।

विश्लेषण

में एक d-एरी हीप के साथ n इसमें वस्तु, ऊपर की ओर-स्वैपिंग प्रक्रिया और नीचे की ओर-स्वैपिंग प्रक्रिया दोनों ही कार्य कर सकते है log_d n = log n / log d अदला-बदली। अपवर्ड-स्वैपिंग प्रक्रिया में, प्रत्येक स्वैप में किसी वस्तु की उसके मूल के साथ एकल तुलना शामिल होती है, और इसमें निरंतर समय लगता है। इसलिए, हीप में एक नया वस्तु डालने, न्यूनतम-हीप में किसी वस्तु की प्राथमिकता को कम करने, या अधिकतम-हीप में किसी वस्तु की प्राथमिकता बढ़ाने का समय है O(log n / log d). डाउनवर्ड-स्वैपिंग प्रक्रिया में, प्रत्येक स्वैप शामिल होता है d तुलना और लेता है O(d) समय: लगता है d − 1 बच्चों की न्यूनतम या अधिकतम संख्या निर्धारित करने के लिए तुलना और फिर माता-पिता के विरुद्ध एक और तुलना यह निर्धारित करने के लिए कि क्या अदला-बदली की आवश्यकता है। इसलिए, रूट वस्तु को हटाने, न्यूनतम-हीप में किसी वस्तु की प्राथमिकता बढ़ाने या अधिकतम-हीप में किसी वस्तु की प्राथमिकता कम करने का समय है O(d log n / log d).

बनाते समय ए d-एन वस्तुओं के एक सेट से हीप, अधिकांश वस्तुएं ऐसी स्थिति में है जो अंततः पत्तियों को धारण करेंगी d-एरी ट्री, और उन वस्तुओं के लिए कोई नीचे की ओर स्वैपिंग नहीं की जाती है। अधिक से अधिक n/d + 1 वस्तु गैर-पत्ते है, और इन्हें कम से कम एक बार लागत पर नीचे की ओर बदला जा सकता है O(d) उनकी अदला-बदली के लिए बच्चे को ढूंढने का समय आ गया है। अधिक से अधिक n/d² + 1 नोड्स को दो बार नीचे की ओर स्वैप किया जा सकता है, जिससे अतिरिक्त खर्च होता है O(d) दूसरे स्वैप की लागत पहले कार्यकाल में पहले से ही गणना की गई लागत से अधिक है, आदि। इसलिए, इस तरह से हीप बनाने में लगने वाला कुल समय है

$\sum _{i=1}^{\log _{d}n}\left({\frac {n}{d^{i}}}+1\right)O(d)=O(n).$

उपरोक्त का सटीक मान (डी-एरी हीप के निर्माण के दौरान तुलना की सबसे खराब स्थिति वाली संख्या) को इसके बराबर माना जाता है:

${\frac {d}{d-1}}(n-s_{d}(n))-(d-1-(n{\bmod {d}}))\left(e_{d}\left(\left\lfloor {\frac {n}{d}}\right\rfloor \right)+1\right)$,

कहाँ एस_d(एन) एन और ई के मानक आधार-डी प्रतिनिधित्व के सभी अंकों का योग है_d(n) n के गुणनखंडन में d का घातांक है।

इससे यह कम हो जाता है

$2n-2s_{2}(n)-e_{2}(n)$,d = 2, और के लिए

${\frac {3}{2}}(n-s_{3}(n))-2e_{3}(n)-e_{3}(n-1)$,

डी = 3 के लिए.

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

अनुप्रयोग

ग्राफ़ (अलग गणित) पर काम करते समय mकिनारे और n कोने, सबसे छोटे पथों के लिए दिज्क्स्ट्रा का एल्गोरिदम और न्यूनतम फैले हुए पेड़ों के लिए प्राइम का एल्गोरिदम दोनों एक न्यूनतम-हीप का उपयोग करते है जिसमें है n डिलीट-मिन ऑपरेशंस और उतने ही m कमी-प्राथमिकता संचालन। ए का उपयोग करके d-एरी हीप के साथ d = m/n, इन दो प्रकार के परिचालनों के लिए कुल समय को एक-दूसरे के विरुद्ध संतुलित किया जा सकता है, जिससे कुल समय प्राप्त हो सकता है O(m log_m/n n) एल्गोरिथम के लिए, में सुधार O(m log n) जब भी किनारों की संख्या शीर्षों की संख्या से काफी बड़ी होती है, तो इन एल्गोरिदम के बाइनरी हीप संस्करणों का चलने का समय। एक वैकल्पिक प्राथमिकता कतार डेटा संरचना, फाइबोनैचि हीप, और भी बेहतर सैद्धांतिक चलने का समय देता है O(m + n log n), लेकिन व्यवहार में d-एरी हीप्स आम तौर पर इस एप्लिकेशन के लिए फाइबोनैचि हीप्स की तुलना में कम से कम तेज़ और अक्सर तेज़ होते है।

व्यवहार में 4-हीप्स बाइनरी हीप्स से बेहतर प्रदर्शन कर सकते है, यहां तक ​​कि डिलीट-मिन ऑपरेशन के लिए भी। इसके अतिरिक्त, ए d-एरी हीप आम तौर पर कंप्यूटर की कैश मैमोरी के आकार से अधिक के हीप आकारों के लिए बाइनरी हीप की तुलना में बहुत तेजी से चलता है: एक बाइनरी हीप के लिए आम तौर पर एक की तुलना में अधिक कैश मिस और आभासी मेमोरी पेज दोष की आवश्यकता होती है d-एरी हीप, प्रत्येक अतिरिक्त तुलना द्वारा किए गए अतिरिक्त कार्य की तुलना में कहीं अधिक समय लेता है d-एरी हीप की तुलना बाइनरी हीप से की जाती है।

बाहरी संबंध

• C++ implementation of generalized heap with D-Heap support