我正在寻找一种数据结构(类似数组),允许
快速(比O(N)更快)任意插入值到结构中.数据结构必须能够以插入方式打印出元素.这类似于List.Insert()(它太慢了,因为它必须移动每个元素),除了我不需要
随机访问或
删除.插入将始终在’数组’的大小范围内.所有值都是唯一的.不需要其他操作.
例如,如果Insert(x,i)在索引i(0-indexing)处插入值x.然后：
>插入(1,0)给出{1}
>插入(3,1)给出{1,3}
>插入(2,2,3}
>插入(5,0)给出{5,1,3}
并且它需要能够在最后打印出{5,3}.
我正在使用C.
使用
skip list.另一个选项应该是
tiered vector.跳过列表在const O(log(n))执行插入并按顺序保存数字.分层向量
支持插入O(sqrt(n))并再次按顺序打印元素.
编辑：根据amit的评论,我将解释如何在跳过列表中找到第k个元素：
对于每个元素,您都有一个指向下一个元素链接的塔,对于每个链接,您知道它跳过了多少个元素.因此,寻找第k个元素,从列表的头部开始,然后沿着塔向下走,直到找到跳过不超过k个元素的链接.您转到此节点指向的节点,并使用跳过的元素数减少k.继续这样做,直到你有k = 0.
