9

以下数据结构有名称吗？有论文和引用吗？

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

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

通常，集合中的数组的大小对应于集合大小的二进制表示中的 1 位。该数据结构是高效的，因为插入可以在平均O (1) 时间内执行，并且搜索可以在O ((log n ) 2 ) 时间内执行（这比线性搜索要好）。此外，它仅使用O (log n ) 空间开销来存储指针，这与平衡二叉树和 B 树不同，它们使用O ( n ) 额外空间来存储指针。因此，几乎所有空间都用于有效载荷数据。

我查看了 Wikipedia 的数据结构列表，但没有找到匹配项。确实，《算法简介》（“CLRS”）一书在“摊销分析”部分将这种数据结构描述为一个家庭作业问题，但由于它是一个问题而不是一个例子，所以这本书并没有多说。

4

1 回答 1

4

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

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

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

于 2013-06-07T17:32:43.087 回答