插入的高效数据结构

Question

我正在寻找一种数据结构(类似数组),允许快速(比O(N)更快)任意插入值到结构中.数据结构必须能够以插入方式打印出元素.这类似于List.Insert()(它太慢了,因为它必须移动每个元素),除了我不需要随机访问或删除.插入将始终在'数组'的大小范围内.所有值都是唯一的.不需要其他操作.

例如,如果Insert(x,i)在索引i(0-indexing)处插入值x.然后:

• 插入(1,0)给出{1}
• 插入(3,1)给出{1,3}
• 插入(2,1)给出{1,2,3}
• 插入(5,0)给出{5,1,2,3}

而且它需要能够在最后打印出{5,1,2,3}.

我正在使用C++.

Answer 1

使用跳过列表.另一种选择应该是分层向量.跳过列表在const O(log(n))执行插入并按顺序保存数字.分层向量支持插入O(sqrt(n))并再次按顺序打印元素.

编辑:根据amit的评论,我将解释如何在跳过列表中找到第k个元素:

对于每个元素,您在下一个元素的链接上都有一个塔,对于每个链接,您知道它跳过了多少个元素.因此,寻找第k个元素,从列表的头部开始,沿着塔向下走,直到找到跳过不超过k个元素的链接.您转到此节点指向的节点,并使用跳过的元素数减少k.继续这样做,直到你有k = 0.