Hug*_*den 11 language-agnostic optimization binary-tree data-structures
我有一系列我将要处理的项目(大理性).在每种情况下,处理将包括删除集合中的最小项目,做一些工作,然后添加0-2个新项目(总是大于删除的项目).该集合将使用一个项目进行初始化,并且工作将继续进行,直到它为空.我不确定该系列可能达到的尺寸,但我希望在1M-100M范围内.我不需要找到除最小项目之外的任何项目.
我目前正计划使用一棵红黑树,可能会调整以保持指向最小项目的指针.但是我之前从未使用过,我不确定我的使用模式是否符合其特性.
1)是否存在从左+随机插入删除模式会影响性能的危险,例如通过要求比随机删除显着更高的旋转次数？或者删除和插入操作仍然是这个使用模式的O(log n)？
2)其他一些数据结构是否会给我带来更好的性能,要么是因为删除模式还是利用了我只需要找到最小项目的事实？
更新:很高兴我问,二进制堆对于这种情况显然是一个更好的解决方案,并且承诺结果很容易实现.
雨果
堆会给你O(1) O(log n)的去除和O(log n)的插入,并且是多比红黑树实现更简单