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

Question

PriorityQueue pq = 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 时，因此不应依赖它。