रेडिक्स हीप

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

आवश्यकताएँ

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

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

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

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

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

1. $b[i]<u[i+1]$ में $u[i]\leq$ कुंजी: $b[i]$ में कुंजियाँ $u[i+1]$ या $u[i]$ में मान के माध्यम से ऊपर या नीचे सीमित होती हैं।
2. $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.