रेडिक्स हीप: Difference between revisions

Latest revision as of 15:04, 28 July 2023

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

आवश्यकताएँ

सभी कुंजियाँ प्राकृतिक संख्याएँ हैं;
मैक्स. कुंजी - मिन. स्थिरांक C के लिए कुंजी $\leq$ C;
एक्सट्रैक्ट-मिन ऑपरेशन मोनोटोनिक है; अर्थात्, क्रमिक एक्स्ट्रैक्ट-मिन कॉल्स द्वारा लौटाए गए मान मोनोटोनिक रूप से बढ़ रहे हैं।

डेटा संरचना का विवरण

इस प्रकार से तीन सबसे महत्वपूर्ण क्षेत्र (कंप्यूटर विज्ञान) निम्नलिखित हैं:

आकार $B:=\lfloor log(C+1)\rfloor +1$ का $b$ , न्यूनतम सूचकांक के रूप में 0 के साथ, बकेट को संग्रहीत करता है;
आकार $B+1$ का $u$ , न्यूनतम सूचकांक के रूप में 0 के साथ, बकेट की (निचली) सीमाओं को संग्रहीत करें;
$bNum$ , हीप में प्रत्येक अवयव $x$ के लिए वह बकेट रखता है जिसमें वह पूर्ण रूप से संग्रहीत है।

उपरोक्त चित्र डेटा संरचना को पूर्ण रूप से दर्शाता है। इस प्रकार से निम्नलिखित अपरिवर्तनीय लागू होते हैं:

$b[i]<u[i+1]$ में $u[i]\leq$ कुंजी: $b[i]$ में कुंजियाँ $u[i+1]$ या $u[i]$ में मान के माध्यम से ऊपर या नीचे सीमित होती हैं।
$i=1,\ldots ,B-1$ के लिए $u[0]=0,u[1]=u[0]+1,u[B]=\infty$ और $0\leq u[i+1]-u[i]\leq 2^{i-1}$ : बकेट का आकार तीव्रता से बढ़ता है।

अतः सीमाओं की घातीय वृद्धि (और इस प्रकार बकेट की सीमा) पर ध्यान देना महत्वपूर्ण है। इस प्रकार क्षेत्र मात्राओं की लघुगणकीय निर्भरता मान C की होती है, जो दो प्रमुख मानों के बीच मैक्स अंतर है।

ऑपरेशन

इस प्रकार से आरंभीकरण के समय, रिक्त बकेट उत्पन्न होते हैं और निचली सीमा $u$ उत्पन्न होती है (अपरिवर्तनीय 2 के अनुसार); रन टाइम $O(B)$ ।

अतः इन्सर्ट के समय, नवीन अवयव $x$ बकेट के माध्यम से दाएं से बाएं ओर रैखिक रूप से ले जाया जाता है और $k(x)$ वाला नवीन अवयव बाएं बकेट में उस $u[i]\geq k(x)$ में संग्रहीत किया जाता है; रन टाइम $O(B)$ ।

इस प्रकार से निम्न-कुंजी के लिए, पहले कुंजी मान घटाया जाता है (अपरिवर्तनीयों के अनुपालन की जाँच करना)। फिर $bNum$ क्षेत्र का उपयोग अवयव का पता लगाने के लिए किया जाता है और यदि आवश्यक हो, तो इसे सम्मिलित ऑपरेशन के अनुरूप बाईं ओर दोहराया जाता है। अतः रन टाइम $O(1)$ (परिशोधन) है।

अतः एक्सट्रेक्ट-मिन ऑपरेशन बकेट $b[0]$ से एक अवयव को हटाता है और उसे वापस कर देता है। इस प्रकार से यदि बकेट $b[0]$ अभी तक रिक्त नहीं है, तो ऑपरेशन पूर्ण रूप से समाप्त हो गया है। यदि, तथापि, यह रिक्त है, तो अगली बड़ी गैर-रिक्त बकेट की खोज की जाती है, इसके सबसे छोटे अवयव $k$ को ट्रैक किया जाता है और $u[0]$ को k पर पूर्ण रूप से समूहित किया जाता है (इसके लिए मोनोटोनिसिटी आवश्यक है)। फिर, अपरिवर्तनीयों के अनुसार, बकेट की सीमाओं को फिर से परिभाषित किया जाता है और अवयवों को नवनिर्मित बकेट $b[i]$ हटा दिया जाता है; रन टाइम $O(1)$ (परिशोधन)।

इस प्रकार से यदि प्रदर्शित होता है, तो क्षेत्र $bNum$ अपडेट किया जाता है।

संदर्भ

B.V. Cherkassky, A.V. Goldberg, C. Silverstein: Buckets, Heaps, Lists and Monotone Priority Queues (Abstract), in: Proceedings of the Eight Annual ACM-SIAM Symposium on Discrete Algorithms. January 1997, pp. 83-92.

@@ Line 1: / Line 1: @@
-रेडिक्स हीप [[मोनोटोन प्राथमिकता कतार]] के संचालन को साकार करने के लिए [[डेटा संरचना]] है। तत्वों का सेट जिसके लिए कुंजी सौंपी गई है, उसे प्रबंधित किया जा सकता है। संचालन का रन टाइम सबसे बड़ी और सबसे छोटी कुंजी या स्थिरांक के बीच के अंतर पर निर्भर करता है। डेटा संरचना में मुख्य रूप से बकेट की श्रृंखला होती है, जिसका आकार तेजी से बढ़ता है।
+'''रेडिक्स हीप''' [[मोनोटोन प्राथमिकता कतार|'''मोनोटोन प्राथमिकता क्यू''']] के ऑपरेशन को समझने के लिए एक [[डेटा संरचना|'''डेटा संरचना''']] है। अवयवों का समूह जिसके लिए कुंजी निर्दिष्ट की गई है, उसे प्रबंधित किया जा सकता है। इस प्रकार से ऑपरेशन का रन टाइम सबसे बड़ी और सबसे छोटी कुंजी या स्थिरांक के बीच के अंतर पर निर्भर करता है। अतः डेटा संरचना में मुख्य रूप से बकेट की श्रृंखला होती है, जिसका आकार तीव्रता से पूर्ण रूप से बढ़ता है।
 ==आवश्यकताएँ==
-# सभी कुंजियाँ [[प्राकृतिक संख्या]]एँ हैं;
+# सभी कुंजियाँ '''[[प्राकृतिक संख्या|प्राकृतिक संख्याएँ]]''' हैं;
-# अधिकतम. कुंजी - न्यूनतम. चाबी <math>\le</math> स्थिरांक C के लिए C;
+# मैक्स. कुंजी - मिन. स्थिरांक C के लिए कुंजी <math>\le</math> C;
-# हीप_(डेटा_स्ट्रक्चर)#ऑपरेशंस|एक्सट्रैक्ट-मिन ऑपरेशन मोनोटोनिक है; अर्थात्, क्रमिक एक्स्ट्रैक्ट-मिन कॉल्स द्वारा लौटाए गए मान एकरस रूप से बढ़ रहे हैं।
+# एक्सट्रैक्ट-मिन ऑपरेशन मोनोटोनिक है; अर्थात्, क्रमिक एक्स्ट्रैक्ट-मिन कॉल्स द्वारा लौटाए गए मान मोनोटोनिक रूप से बढ़ रहे हैं।
 ==डेटा संरचना का विवरण==
-तीन सबसे महत्वपूर्ण [[क्षेत्र (कंप्यूटर विज्ञान)]] हैं:
+इस प्रकार से तीन सबसे महत्वपूर्ण [[क्षेत्र (कंप्यूटर विज्ञान)]] निम्नलिखित हैं:
-# <math>b</math> आकार का <math>B := \lfloor log(C+1)\rfloor + 1</math>, न्यूनतम सूचकांक के रूप में 0 के साथ, बाल्टियाँ संग्रहीत करता है;
+# आकार <math>B := \lfloor log(C+1)\rfloor + 1</math> का <math>b</math>, न्यूनतम सूचकांक के रूप में '''0''' के साथ, बकेट को संग्रहीत करता है;
-# <math>u</math> आकार का <math>B+1</math>, न्यूनतम सूचकांक के रूप में 0 के साथ, बाल्टियों की (निचली) सीमाओं को संग्रहीत करें;
+# आकार <math>B+1</math> का <math>u</math>, न्यूनतम सूचकांक के रूप में '''0''' के साथ, बकेट की (निचली) सीमाओं को संग्रहीत करें;
-# <math>bNum</math>, प्रत्येक तत्व के लिए धारण करता है <math>x</math> ढेर में वह बाल्टी जिसमें वह संग्रहीत है।
+# '''<math>bNum</math>''', हीप में प्रत्येक अवयव <math>x</math> के लिए वह बकेट रखता है जिसमें वह पूर्ण रूप से संग्रहीत है।
-[[Image:RadixHeap1.png]]उपरोक्त चित्र डेटा संरचना को दर्शाता है। निम्नलिखित अपरिवर्तनीय लागू होते हैं:
+'''[[Image:RadixHeap1.png]]'''
-# <math>u[i] \le</math> में कुंजी <math>b[i] < u[i+1]</math>: अंदर की चाबियाँ <math>b[i]</math> में मान के माध्यम से ऊपर या नीचे होते हैं <math>u[i+1]</math> या <math>u[i]</math> सीमित।
+उपरोक्त चित्र डेटा संरचना को पूर्ण रूप से दर्शाता है। इस प्रकार से निम्नलिखित अपरिवर्तनीय लागू होते हैं:
-# <math>u[0] = 0, u[1] = u[0] + 1, u[B] = \infty</math> और <math>0 \le u[i+1]-u[i] \le 2^{i-1}</math> के लिए <math>i = 1, \ldots, B-1</math>: बाल्टियों का आकार तेजी से बढ़ता है।
-सीमाओं की घातीय वृद्धि (और इस प्रकार बाल्टी की सीमा) पर ध्यान देना महत्वपूर्ण है। इस प्रकार फ़ील्ड मात्राओं की लघुगणकीय निर्भरता मान C की होती है, जो दो प्रमुख मानों के बीच अधिकतम अंतर है।
+# <math>b[i] < u[i+1]</math> में <math>u[i] \le</math> कुंजी: <math>b[i]</math> में कुंजियाँ <math>u[i+1]</math> या <math>u[i]</math> में मान के माध्यम से ऊपर या नीचे सीमित होती हैं।
+# <math>i = 1, \ldots, B-1</math> के लिए <math>u[0] = 0, u[1] = u[0] + 1, u[B] = \infty</math> और <math>0 \le u[i+1]-u[i] \le 2^{i-1}</math>: बकेट का आकार तीव्रता से बढ़ता है।
-==संचालन==
+अतः सीमाओं की घातीय वृद्धि (और इस प्रकार बकेट की सीमा) पर ध्यान देना महत्वपूर्ण है। इस प्रकार क्षेत्र मात्राओं की लघुगणकीय निर्भरता मान '''C''' की होती है, जो दो प्रमुख मानों के बीच मैक्स अंतर है।
-आरंभीकरण के दौरान, खाली बकेट और निचली सीमाएं उत्पन्न होती हैं <math>u</math> उत्पन्न होते हैं (अपरिवर्तनीय 2 के अनुसार); कार्यकारी समय <math>O(B)</math>.
+==ऑपरेशन==
-सम्मिलित करते समय, नया तत्व <math>x</math> बाल्टियों और नए तत्व के माध्यम से रैखिक रूप से दाएं से बाएं ओर ले जाया जाता है <math>k(x)</math> उसके बायीं ओर की बाल्टी में संग्रहित किया जाता है <math>u[i] \ge k(x)</math>; कार्यकारी समय <math>O(B)</math>.
+इस प्रकार से आरंभीकरण के समय, रिक्त बकेट उत्पन्न होते हैं और निचली सीमा <math>u</math> उत्पन्न होती है (अपरिवर्तनीय '''2''' के अनुसार); रन टाइम <math>O(B)</math>।
-कमी-कुंजी के लिए, पहले कुंजी मान घटाया जाता है (अपरिवर्तनीयों के अनुपालन की जाँच करना)। फिर <math>bNum</math> फ़ील्ड का उपयोग तत्व का पता लगाने के लिए किया जाता है और यदि आवश्यक हो, तो इसे सम्मिलित ऑपरेशन के अनुरूप बाईं ओर दोहराया जाता है। चलने का समय है <math>O(1)</math> (परिशोधन)।
+अतः इन्सर्ट के समय, नवीन अवयव <math>x</math> बकेट के माध्यम से दाएं से बाएं ओर रैखिक रूप से ले जाया जाता है और <math>k(x)</math> वाला नवीन अवयव बाएं बकेट में उस <math>u[i] \ge k(x)</math> में संग्रहीत किया जाता है; रन टाइम <math>O(B)</math>।
-एक्सट्रेक्ट-मिन ऑपरेशन बकेट से तत्व को हटा देता है <math>b[0]</math> और उसे वापस कर देता है. यदि बाल्टी <math>b[0]</math> अभी तक खाली नहीं है, कार्रवाई समाप्त हो गई है। यदि, तथापि, यह खाली है, तो अगली बड़ी गैर-रिक्त बाल्टी की खोज की जाती है, जो इसका सबसे छोटा तत्व है <math>k</math> ट्रैक किया गया और <math>u[0]</math> k पर सेट है (इसके लिए नीरसता आवश्यक है)। फिर, अपरिवर्तनीयों के अनुसार, बाल्टी की सीमाओं को फिर से परिभाषित किया जाता है और तत्वों को हटा दिया जाता है <math>b[i]</math> नवगठित बाल्टियों के लिए; कार्यकारी समय <math>O(1)</math> (परिशोधन)।
+इस प्रकार से निम्न-कुंजी के लिए, पहले कुंजी मान घटाया जाता है (अपरिवर्तनीयों के अनुपालन की जाँच करना)। फिर <math>bNum</math> क्षेत्र का उपयोग अवयव का पता लगाने के लिए किया जाता है और यदि आवश्यक हो, तो इसे सम्मिलित ऑपरेशन के अनुरूप बाईं ओर दोहराया जाता है। अतः रन टाइम <math>O(1)</math> (परिशोधन) है।
-यदि प्रदर्शित हो, तो फ़ील्ड <math>bNum</math> यह अद्यतित है।
+अतः एक्सट्रेक्ट-मिन ऑपरेशन बकेट <math>b[0]</math> से एक अवयव को हटाता है और उसे वापस कर देता है। इस प्रकार से यदि बकेट <math>b[0]</math> अभी तक रिक्त नहीं है, तो ऑपरेशन पूर्ण रूप से समाप्त हो गया है। यदि, तथापि, यह रिक्त है, तो अगली बड़ी गैर-रिक्त बकेट की खोज की जाती है, इसके सबसे छोटे अवयव <math>k</math> को ट्रैक किया जाता है और <math>u[0]</math> को '''k''' पर पूर्ण रूप से समूहित किया जाता है (इसके लिए मोनोटोनिसिटी आवश्यक है)। फिर, अपरिवर्तनीयों के अनुसार, बकेट की सीमाओं को फिर से परिभाषित किया जाता है और अवयवों को नवनिर्मित बकेट <math>b[i]</math> हटा दिया जाता है; रन टाइम <math>O(1)</math> (परिशोधन)।
+इस प्रकार से यदि प्रदर्शित होता है, तो क्षेत्र <math>bNum</math> अपडेट किया जाता है।
 ==संदर्भ==
 * B.V. Cherkassky, A.V. Goldberg, C. Silverstein: [http://xenon.stanford.edu/~csilvers/papers/hotq-soda.ps ''Buckets, Heaps, Lists and Monotone Priority Queues''] ([http://xenon.stanford.edu/~csilvers/papers/hotq-soda-abstract.txt Abstract]), in: Proceedings of the Eight Annual ACM-SIAM Symposium on Discrete Algorithms. January 1997, pp. 83-92.
-[[Category: ढेर (डेटा संरचनाएं)]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 10/07/2023]]
+[[Category:Machine Translated Page]]
+[[Category:ढेर (डेटा संरचनाएं)]]

Anonymous

Search

रेडिक्स हीप: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 15:04, 28 July 2023

Contents

आवश्यकताएँ

डेटा संरचना का विवरण

ऑपरेशन

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

रेडिक्स हीप: Difference between revisions

Latest revision as of 15:04, 28 July 2023

आवश्यकताएँ

डेटा संरचना का विवरण

ऑपरेशन

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Hidden categories