Java PriorityQueue.remove() 时间复杂度?O(log N) 还是 O(N)?

Question

PriorityQueuepq = new PriorityQueue<>((; 假设 priorityQueue pq 的大小为 N，pq.remove(( 的时间复杂度是多少？

是O(log N(还是O(N(？

Answer 1

来自PriorityQueue的文档：

[...]

实现说明：此实现为排队和出列方法(offer、poll、remove()和add(提供了O(log(n((时间;为remove(Object)和contains(Object)方法提供了线性时间;为检索方法(peek、element和size(提供了恒定时间。

[...]

但是，应该指出的是，这不是任何接口合约的一部分。因此，它是一个实现细节。因此，它可能会更改，恕不另行通知，或者在使用非Oracle JDK时进行更改，因此不应依赖它。