सॉर्ट किए गए सरणी डेटा संरचना के इस संग्रह के लिए कोई नाम है?

Question

क्या निम्न डेटा संरचना के लिए कोई नाम है? क्या कागजात और उद्धरण उपलब्ध हैं?

एक तरह से to implement एक कुशल सेट सार डेटा प्रकार क्रमबद्ध सरणियों का एक संग्रह है, जहां प्रत्येक सरणी के लिए एक अनूठा बिजली के- 2 आकार की है है।

उदाहरण के लिए, 13 तत्वों का एक सेट {1, 2, ..., 13} सॉर्ट किए गए सरणी के इस संग्रह द्वारा प्रदर्शित किया जा सकता है: {[5], [2, 3, 9, 13], [1 , 4, 6, 7, 8, 10, 11, 12]}।

सामान्य रूप से, संग्रह में मौजूद सरणी के आकार होते हैं जो सेट के आकार के द्विआधारी प्रतिनिधित्व में 1 बिट्स के अनुरूप होते हैं। डेटा संरचना कुशल है, क्योंकि प्रविष्टि परिशोधित हे (1) समय में किया जा सकता है, और खोज हे में किया जा सकता ((लॉग n)) समय (जो रैखिक खोज की तुलना में बेहतर है)। इसके अलावा, यह केवल हे (लॉग n) संकेत के लिए जगह भूमि के ऊपर का उपयोग करता है, संतुलित द्विआधारी पेड़ और बी पेड़ जो हे (n) संकेत के लिए अतिरिक्त जगह का उपयोग के विपरीत है। इस प्रकार, लगभग सभी जगह पेलोड डेटा के लिए उपयोग की जाती है।

मैंने विकिपीडिया के list of data structures पर देखा है लेकिन एक मैच नहीं मिला। यह सच है कि पुस्तक का परिचय एल्गोरिदम ("सीएलआरएस") इस डेटा संरचना को "अमूर्त विश्लेषण" खंड में होमवर्क समस्या के रूप में वर्णित करता है, लेकिन क्योंकि यह एक उदाहरण के बजाय एक प्रश्न है, पुस्तक इसके बारे में ज्यादा कुछ नहीं कहती है।

Answer 1

सीएसीएम के अप्रैल 1 9 78 के अंक में कम से कम एक ही विचार जीन विलिमिन के original publication on binomial heaps पर वापस आता है। मैं उस पेपर की अपेक्षा करता हूं जिसने इस डेटा संरचना को उद्धृत करने या उद्धृत करने के लिए विलिमिन द्वारा उद्धृत किया है, लेकिन "संदर्भ" और "उद्धृत" सूचियों पर कोई भी कागजात आशाजनक नहीं दिखता है।

यदि मैं आप थे, तो मैं cstheory से पूछूंगा और फिर सीएलआरएस को लिखूंगा, लेकिन उप-सीमाबद्ध सीमाओं और हटाने की कमी के कारण, मुझे कुछ भी उम्मीद नहीं है जब तक succinct data structure समुदाय ने किसी बिंदु पर कोई दिलचस्पी नहीं ली।

क्या आप विशेष रूप से कुछ जानना चाहते हैं?