在RDring上测试后，我发现有时remove element会失败， 删除定时器的时间复杂度是线性的；警报管理器使用 TreeSet 迭代所有元素以进行删除。
然后，我查看了 PriorityQueue 的来源，猜测也许可以用它来存储计时器 列表。但令我感到非常惊讶的是，尽管 PriorityQueue 中的删除是在 常数时间，优先级队列中元素的插入也是线性的。 他们没有使用任何树或某种二进制搜索技术来加速 插入。
如果我想快速删除，那么 PQ 但插入慢。否则我可以使用 TreeSet 用于插入 log-N 但删除速度较慢。是否有支持的树或堆 以 log-N 速度插入、删除和查找？
最佳答案
Is there any tree or heap that support both insert, delete and find in log-N speed ?
是的，基于红黑树TreeMap保证:
Class TreeMap<K,V>
...
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.
另见
- What are the time complexities of various data structures?为了很好地概述各种数据结构的时间复杂性。相应 Java 实现的复杂性通常记录在相应的 JavaDoc 中。
- Java Collections – Performance (Time Complexity)对 JDK 容器类有很好的概述。
顺便说一下，您说使用 TreeSet，删除速度很慢 - 然而，JavaDoc还记录了用于删除的 O(log(n)):
Class TreeSet<E>
...
This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).
关于java - JDK中有没有一种数据结构可以做到log-N次的remove、find和insert？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26795283/