रेडिक्स हीप

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

आवश्यकताएँ

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

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

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

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

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

1. $u[i]\leq$ में कुंजी $b[i]<u[i+1]$: अंदर की चाबियाँ $b[i]$ में मान के माध्यम से ऊपर या नीचे होते हैं $u[i+1]$ या $u[i]$ सीमित।
2. $u[0]=0,u[1]=u[0]+1,u[B]=\infty$ और $0\leq u[i+1]-u[i]\leq 2^{i-1}$ के लिए $i=1,\ldots ,B-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.