在对RDring进行测试后,我发现删除元素有时失败,删除定时器的时间复杂度是线性的; 警报管理器使用TreeSet迭代所有要删除的元素.
然后,我查看PriorityQueue的来源并猜测也许可以用它来存储计时器列表.但我很惊讶,虽然PriorityQueue中的删除是在恒定时间内,但优先级队列中的元素插入也是线性的.他们没有使用任何树或二进制搜索技术来加速插入.
如果我想快速删除,那么PQ但插入慢.否则我可以使用TreeSet在log-N中插入但删除缓慢.是否有任何树或堆支持以log-N速度插入,删除和查找？
是否有任何树或堆支持以log-N速度插入,删除和查找？
是的,基于红黑树的TreeMap保证:
类TreeMap <K,V>
...
此实现为containsKey,get,put和remove操作提供有保证的log(n)时间成本.算法是Cormen,Leiserson和Rivest的算法导论中的算法的改编.
也可以看看
顺便说一句,你说TreeSet,删除速度很慢 - 但是,JavaDoc也会O(log(n))删除文件:
类TreeSet <E>
...
此实现为基本操作(添加,删除和包含)提供了有保证的log(n)时间成本.