这个排序数组数据结构的名称是否有名称？

Question

是否有以下数据结构的名称？是否有论文和引文？

实现高效集抽象数据类型的一种方法是具有排序数组的集合,其中每个数组具有唯一的2次幂大小.

例如,一组13个元素{1,2,...,13}可以由这个排序数组集合表示:{[5],[2,3,9,13],[1,4,6] ,7,8,10,11,12]}.

通常,集合中的数组的大小对应于集合大小的二进制表示中的1位.数据结构是有效的,因为插入可以在分摊的O(1)时间内执行,并且搜索可以在O((log n)²)时间内执行(这比线性搜索更好).此外,它仅对指针使用O(log n)空间开销,这与平衡二进制树和使用O(n)额外空间用于指针的B树不同.因此,几乎所有空间都用于有效载荷数据.

我查看了维基百科的数据结构列表,但未找到匹配项.确实,"算法导论"("CLRS")将这种数据结构描述为"摊销分析"部分中的作业问题,但由于这是一个问题而不是一个例子,因此本书并没有多说.

Answer 1

类似的想法至少可以追溯到 Jean Vuillemin在 1978 年 4 月号 CACM 上发表的有关二项式堆的原始文章。我希望介绍这种数据结构的论文能够被 Vuillemin 引用或被引用，但“参考文献”和“被引用”列表中的论文看起来都没有前景。

如果我是你，我会询问cstheory，然后写信给 CLRS，但考虑到次优边界和缺乏删除，我不希望出现任何结果，除非简洁数据结构社区在某个时候对此感兴趣。

您有什么特别想知道的吗？