排序结构，快速插入和头部/地板删除许多元素

Question

插入和删除高于/小于或等于给定值的许多元素的最快排序结构是什么?我将用几个步骤来描述它:

1. 起始点= [1,2,3]
2. 新值5 = [1,2,3,5]
3. 下一个新值4 = [1,2,3,4,5]
4. 下一个新值4再次=[1,2,3,4,4,5](4的处理方式相同)
5. removeTail(4) =[1,2,3](它返回被删除的元素:[4,4,5]
6. removeHead(2) =[3](它返回被删除的元素:[1,2]

结构将从单线程访问，内存消耗无关紧要。我想达到最快(至少0 (logN))的复杂度。我想知道我是否应该使用一些b树，但似乎太多的重新平衡开销，所以也许我应该尝试跳过列表?

Answer 1

如果您对这些操作的可能的O(logn)性能满意，那么一个简单的概率跳表在这里听起来很完美。

插入和删除是Skip List自带的。

RemoveTail()和RemoveHead()只是找到元素，并修剪其上方的所有元素;(在它上面，我指的是用于查找元素的实际路径)向左或向右。每个这样的操作平均是O(logn)，因为您只接触路径中的节点(每个节点可能有一个相邻节点)。

如果你想要确定性-这也可以做到，但是在保持确定性结构的同时删除元素和重新平衡会更复杂，尽管不是不可能的。