具有快速插入和 head/floor 删除许多元素的排序结构
Sorted structure with fast insertion and head/floor removal many elements
对于插入和移除许多元素 higher/lesser 或等于给定值，最快的排序结构是什么？我将分几步描述它：
- 起点 = [1,2,3]
- 新值 5 = [1,2,3,5]
- 下一个新值 4 = [1,2,3,4,5]
- 下一个新值 4 = [1,2,3,4,4,5]（4 的处理方式相同）
- removeTail(4) = [1,2,3]（它 returns 删除元素：[4,4,5]
- removeHead(2) = [3]（它 returns 删除了元素：[1,2]
该结构将从单线程访问，内存消耗无关紧要。我想达到最快的（至少 O(logN)）复杂度。我想知道我是否应该使用一些 B 树，但重新平衡开销似乎太多，所以也许我应该尝试跳过列表？
如果您对每个操作的 likely O(logn) 性能没问题，那么这里的简单概率 skip list 听起来很完美。
插入和删除是跳过列表的原生功能。
RemoveTail() 和 RemoveHead() 只是找到元素，并将“在它上面”的所有内容（在它上面，我的意思是你用来找到元素的实际路径）修剪到左边或向右。每个这样的操作平均是 O(logn)，因为您只接触路径中的节点（可能每个节点都有一个相邻节点）。
如果您想要确定性 - 这也可以做到，但是在保持确定性结构的同时删除元素和重新平衡会更加复杂，尽管并非不可能。
对于插入和移除许多元素 higher/lesser 或等于给定值，最快的排序结构是什么？我将分几步描述它：
- 起点 = [1,2,3]
- 新值 5 = [1,2,3,5]
- 下一个新值 4 = [1,2,3,4,5]
- 下一个新值 4 = [1,2,3,4,4,5]（4 的处理方式相同）
- removeTail(4) = [1,2,3]（它 returns 删除元素：[4,4,5]
- removeHead(2) = [3]（它 returns 删除了元素：[1,2]
该结构将从单线程访问，内存消耗无关紧要。我想达到最快的（至少 O(logN)）复杂度。我想知道我是否应该使用一些 B 树，但重新平衡开销似乎太多，所以也许我应该尝试跳过列表？
如果您对每个操作的 likely O(logn) 性能没问题，那么这里的简单概率 skip list 听起来很完美。
插入和删除是跳过列表的原生功能。
RemoveTail() 和 RemoveHead() 只是找到元素，并将“在它上面”的所有内容（在它上面，我的意思是你用来找到元素的实际路径）修剪到左边或向右。每个这样的操作平均是 O(logn)，因为您只接触路径中的节点（可能每个节点都有一个相邻节点）。
如果您想要确定性 - 这也可以做到，但是在保持确定性结构的同时删除元素和重新平衡会更加复杂，尽管并非不可能。