我想知道是否有一种简单的数据结构,支持摊销O(log n)的查找和插入操作,就像自平衡二叉搜索树一样,但是内存开销为常量。(我不太在意删除元素。)
我的一个想法是将所有元素存储在一个连续的内存块中,分成两个连续的块:一个S部分,其中所有元素都已排序,还有一个未排序的U部分。
要执行插入操作,我们可以将一个元素添加到U中,如果U的大小超过了log(S的大小),则对整个连续数组进行排序(将S和U都视为一个连续的数组),以便在排序之后,所有内容都在S中,而U为空。
要执行查找操作,请在S上运行二进制搜索,并查看所有U中的内容。
然而,我在计算我的算法的摊销插入时间时遇到了麻烦。
最终,我只需要一些具有所需属性的相当简单的算法/数据结构,并保证它以摊销时间运行得相当快。
谢谢!
我的一个想法是将所有元素存储在一个连续的内存块中,分成两个连续的块:一个S部分,其中所有元素都已排序,还有一个未排序的U部分。
要执行插入操作,我们可以将一个元素添加到U中,如果U的大小超过了log(S的大小),则对整个连续数组进行排序(将S和U都视为一个连续的数组),以便在排序之后,所有内容都在S中,而U为空。
要执行查找操作,请在S上运行二进制搜索,并查看所有U中的内容。
然而,我在计算我的算法的摊销插入时间时遇到了麻烦。
最终,我只需要一些具有所需属性的相当简单的算法/数据结构,并保证它以摊销时间运行得相当快。
谢谢!