java - 优先队列去除复杂性时间

Question

Java 中 Priority Queue 类上的 remove() 函数的复杂度是多少？我在任何地方都找不到任何文档，我认为它是 O(n)，考虑到您必须在删除它之前找到该元素，然后重新调整树。但我看到其他人不同意并认为这是 O(logn)。有什么想法吗？

Answer 1

混淆实际上是由您的“删除”功能引起的。在java中，有两个remove函数。

1. remove() -> 这是删除头/根，需要 O(logN) 时间。

2. remove(Object o) -> 这是删除任意对象。找到这个对象需要 O(N) 时间，删除它需要 O(logN) 时间。