डी-एरी हीप

$d$ -एरी ढेर या $d$ -हीप एक प्राथमिकता कतार डेटा संरचना है, जो बाइनरी ढेर का एक सामान्यीकरण है जिसमें नोड्स होते हैं $d$ 2 के बजाय बच्चे।^[1]^[2]^[3]इस प्रकार, एक बाइनरी ढेर 2-ढेर है, और एक टर्नरी ढेर 3-ढेर है। टारजन के अनुसार^[2]और जेन्सेन एट अल.,^[4] $d$ -एरी हीप्स का आविष्कार डोनाल्ड बी. जॉनसन ने 1975 में किया था।^[1] यह डेटा संरचना धीमी प्राथमिकता वाले ऑपरेशनों को बाइनरी हीप्स की तुलना में अधिक तेज़ी से निष्पादित करने की अनुमति देती है, धीमे डिलीट न्यूनतम ऑपरेशन की कीमत पर। यह ट्रेडऑफ़ दिज्क्स्ट्रा के एल्गोरिदम जैसे एल्गोरिदम के लिए बेहतर चलने वाले समय की ओर ले जाता है जिसमें प्राथमिकता वाले ऑपरेशन डिलीट मिन ऑपरेशंस की तुलना में अधिक सामान्य होते हैं।^[1]^[5]इसके अतिरिक्त, $d$ -एरी हीप्स में बाइनरी हीप्स की तुलना में बेहतर मेमोरी कैश व्यवहार होता है, जो उन्हें सैद्धांतिक रूप से बड़े सबसे खराब स्थिति वाले रनिंग टाइम के बावजूद व्यवहार में अधिक तेज़ी से चलाने की अनुमति देता है।^[6]बाइनरी ढेर की तरह, $d$ -एरी हीप्स एक इन-प्लेस एल्गोरिदम |इन-प्लेस डेटा संरचना है जो हीप में आइटमों की श्रृंखला को संग्रहीत करने के लिए आवश्यक अतिरिक्त भंडारण का उपयोग नहीं करती है।^[2]^[7]

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

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

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

किसी सारणी से एक नया ढेर बनाने के लिए $n$ आइटम, कोई आइटम की स्थिति से शुरू करते हुए, रिवर्स ऑर्डर में आइटम पर लूप कर सकता है $n - 1$ और आइटम को स्थिति 0 पर समाप्त करते हुए, प्रत्येक आइटम के लिए डाउनवर्ड-स्वैपिंग प्रक्रिया को लागू करना।^[2]^[3]

विश्लेषण

में एक $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)$ .^[2]^[3]

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

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

^[2]^[3]

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

{\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)

,^[8]

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

2n-2s_{2}(n)-e_{2}(n)

,^[8]d = 2, और के लिए

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

,^[8]

डी = 3 के लिए.

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

अनुप्रयोग

ग्राफ़ (अलग गणित) पर काम करते समय $m$ किनारे और $n$ कोने, सबसे छोटे पथों के लिए दिज्क्स्ट्रा का एल्गोरिदम और न्यूनतम फैले हुए पेड़ों के लिए प्राइम का एल्गोरिदम दोनों एक न्यूनतम-ढेर का उपयोग करते हैं जिसमें हैं $n$ डिलीट-मिन ऑपरेशंस और उतने ही $m$ कमी-प्राथमिकता संचालन। ए का उपयोग करके $d$ -एरी ढेर के साथ $d = m / n$ , इन दो प्रकार के परिचालनों के लिए कुल समय को एक-दूसरे के विरुद्ध संतुलित किया जा सकता है, जिससे कुल समय प्राप्त हो सकता है $O(m log m / n n)$ एल्गोरिथम के लिए, में सुधार $O(m log n)$ जब भी किनारों की संख्या शीर्षों की संख्या से काफी बड़ी होती है, तो इन एल्गोरिदम के बाइनरी हीप संस्करणों का चलने का समय।^[1]^[5] एक वैकल्पिक प्राथमिकता कतार डेटा संरचना, फाइबोनैचि हीप, और भी बेहतर सैद्धांतिक चलने का समय देता है $O(m + n log n)$ , लेकिन व्यवहार में $d$ -एरी हीप्स आम तौर पर इस एप्लिकेशन के लिए फाइबोनैचि हीप्स की तुलना में कम से कम तेज़ और अक्सर तेज़ होते हैं।^[9] व्यवहार में 4-हीप्स बाइनरी हीप्स से बेहतर प्रदर्शन कर सकते हैं, यहां तक कि डिलीट-मिन ऑपरेशन के लिए भी।^[2]^[3] इसके अतिरिक्त, ए $d$ -एरी हीप आम तौर पर कंप्यूटर की कैश मैमोरी के आकार से अधिक के हीप आकारों के लिए बाइनरी हीप की तुलना में बहुत तेजी से चलता है: एक बाइनरी हीप के लिए आम तौर पर एक की तुलना में अधिक कैश मिस और आभासी मेमोरी पेज दोष की आवश्यकता होती है $d$ -एरी ढेर, प्रत्येक अतिरिक्त तुलना द्वारा किए गए अतिरिक्त कार्य की तुलना में कहीं अधिक समय लेता है $d$ -एरी हीप की तुलना बाइनरी हीप से की जाती है।^[6]^[10]

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 Johnson, D. B. (1975), "Priority queues with update and finding minimum spanning trees", Information Processing Letters, 4 (3): 53–57, doi:10.1016/0020-0190(75)90001-0.
↑ ^2.00 ^2.01 ^2.02 ^2.03 ^2.04 ^2.05 ^2.06 ^2.07 ^2.08 ^2.09 ^2.10 ^2.11 Tarjan, R. E. (1983), "3.2. d-heaps", Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial and Applied Mathematics, pp. 34–38. Note that Tarjan uses 1-based numbering, not 0-based numbering, so his formulas for the parent and children of a node need to be adjusted when 0-based numbering is used.
↑ ^3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 ^3.6 ^3.7 Weiss, M. A. (2007), "d-heaps", Data Structures and Algorithm Analysis (2nd ed.), Addison-Wesley, p. 216, ISBN 0-321-37013-9.
↑ Jensen, C.; Katajainen, J.; Vitale, F. (2004), An extended truth about heaps (PDF).
↑ ^5.0 ^5.1 Tarjan (1983), pp. 77 and 91.
↑ ^6.0 ^6.1 Naor, D.; Martel, C. U.; Matloff, N. S. (October 1991), "Performance of priority queue structures in a virtual memory environment", Computer Journal, 34 (5): 428–437, doi:10.1093/comjnl/34.5.428.
↑ ^7.0 ^7.1 Mortensen, C. W.; Pettie, S. (2005), "The complexity of implicit and space efficient priority queues", Algorithms and Data Structures: 9th International Workshop, WADS 2005, Waterloo, Canada, August 15–17, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3608, Springer-Verlag, pp. 49–60, doi:10.1007/11534273_6, ISBN 978-3-540-28101-6.
↑ ^8.0 ^8.1 ^8.2 Suchenek, Marek A. (2012), "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program", Fundamenta Informaticae, IOS Press, 120 (1): 75–92, doi:10.3233/FI-2012-751.
↑ Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (May 1996), "Shortest paths algorithms: Theory and experimental evaluation", Mathematical Programming, 73 (2): 129–174, CiteSeerX 10.1.1.48.752, doi:10.1007/BF02592101.
↑ Kamp, Poul-Henning (11 June 2010), "You're doing it wrong", ACM Queue, 8 (6).

बाहरी संबंध

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

[j75-1] 1.0 ^1.1 ^1.2 ^1.3 Johnson, D. B. (1975), "Priority queues with update and finding minimum spanning trees", Information Processing Letters, 4 (3): 53–57, doi:10.1016/0020-0190(75)90001-0.

[t83-2] 2.00 ^2.01 ^2.02 ^2.03 ^2.04 ^2.05 ^2.06 ^2.07 ^2.08 ^2.09 ^2.10 ^2.11 Tarjan, R. E. (1983), "3.2. d-heaps", Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial and Applied Mathematics, pp. 34–38. Note that Tarjan uses 1-based numbering, not 0-based numbering, so his formulas for the parent and children of a node need to be adjusted when 0-based numbering is used.

[w07-3] 3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 ^3.6 ^3.7 Weiss, M. A. (2007), "d-heaps", Data Structures and Algorithm Analysis (2nd ed.), Addison-Wesley, p. 216, ISBN 0-321-37013-9.

[4] Jensen, C.; Katajainen, J.; Vitale, F. (2004), An extended truth about heaps (PDF).

[t2-5] 5.0 ^5.1 Tarjan (1983), pp. 77 and 91.

[nmm91-6] 6.0 ^6.1 Naor, D.; Martel, C. U.; Matloff, N. S. (October 1991), "Performance of priority queue structures in a virtual memory environment", Computer Journal, 34 (5): 428–437, doi:10.1093/comjnl/34.5.428.

[mp05-7] 7.0 ^7.1 Mortensen, C. W.; Pettie, S. (2005), "The complexity of implicit and space efficient priority queues", Algorithms and Data Structures: 9th International Workshop, WADS 2005, Waterloo, Canada, August 15–17, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3608, Springer-Verlag, pp. 49–60, doi:10.1007/11534273_6, ISBN 978-3-540-28101-6.

[Suchenek-8] 8.0 ^8.1 ^8.2 Suchenek, Marek A. (2012), "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program", Fundamenta Informaticae, IOS Press, 120 (1): 75–92, doi:10.3233/FI-2012-751.

[9] Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (May 1996), "Shortest paths algorithms: Theory and experimental evaluation", Mathematical Programming, 73 (2): 129–174, CiteSeerX 10.1.1.48.752, doi:10.1007/BF02592101.

[k10-10] Kamp, Poul-Henning (11 June 2010), "You're doing it wrong", ACM Queue, 8 (6).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Anonymous

Search

डी-एरी हीप

Namespaces

More

Page actions

Contents

विश्लेषण

अनुप्रयोग

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

डी-एरी हीप

विश्लेषण

अनुप्रयोग

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories