语言无关 – 我的理想数据结构是红黑树吗?

我有一个收集的项目(大理性),我将处理.在每种情况下,处理将包括删除集合中最小的项目,做一些工作,然后添加0-2个新项目(这将始终大于删除的项目).该集合将被初始化一个项目,工作将继续,直到它为空.我不知道这个收藏有多大可能达到,但是我期望在1M-100M的范围内.我不需要找到最小的项目.

我目前正在计划使用一个红黑色的树,可能会调整,以保持指向最小的项目.不过我以前从来没有使用过,我不知道我的使用方式是否适合其特性.

1)是否存在从左随机插入中删除的模式会影响性能的危险,例如要求比随机删除显着更高的转数?或者将删除和插入操作仍然是O(log n)与这种使用模式?

2)其他一些数据结构会给我更好的表现,无论是因为删除模式还是利用我只需要找到最小项目的事实?

更新:很高兴我问,这个二进制堆显然是一个更好的解决方案,而且承诺变得非常容易实现.

雨果

一个 binary heap是更好的你想要的.它更容易实现和更快速,因为您只需要定位最小的元素和插入.找到最小元素是O(1),删除它是O(log N),插入也是O(log N).
相关文章
相关标签/搜索