language-agnostic - 红黑树是我理想的数据结构吗？

Question

我有一组我将要处理的项目(大理性)。在每种情况下，处理都包括删除集合中最小的项目，做一些工作，然后添加 0-2 个新项目(它们总是比删除的项目大)。集合将用一个项目初始化，并且工作将继续直到它为空。我不确定该系列可能会达到什么规模，但我希望有 100 万到 100 万件物品。除了最小的物品之外，我不需要找到任何物品。

我目前计划使用红黑树，可能会进行调整以保持指向最小项目的指针。但是我以前从未使用过，我不确定我的使用模式是否适合它的特性。

1) 从左侧删除 + 随机插入的模式是否存在影响性能的危险，例如，需要比随机删除显着更多的旋转次数？或者使用这种使用模式，删除和插入操作仍然是 O(log n) 吗？

2)其他数据结构是否会给我更好的性能，要么是因为删除模式，要么是利用我只需要找到最小项目的事实？

更新:很高兴我问了，二进制堆显然是这种情况下更好的解决方案，而且正如所 promise 的那样，实现起来非常容易。

雨果

Answer 1

binary heap对你想要的要好得多。由于您只关心定位最小的元素和插入，因此更容易实现且更快。定位最小元素是O(1)，移除它是O(log N)，插入也是O(log N)。