内置的 PriorityQueue remove() 函数如何在 java 中找到要删除的所需元素

Question

删除方法：-
public remove()：此方法从队列中删除指定元素的单个实例（如果存在）

remove 方法在 O(1) 中有效吗？如果是这样

它如何找到特定元素

由于优先级队列使用数组且未排序，因此我们不能使用二分查找，而线性查找是一项开销很大的操作。

它是如何工作的？

PriorityQueue<String> queue = new PriorityQueue<String>(); 

// Use add() method to add elements into the Queue 
queue.add("Welcome"); 
queue.add("To"); 
queue.add("Overflow"); 

queue.remove("To");

remove 方法如何在 priorityqueue 数组 {"Overflow","Welcome","To"} 中找到“To”（未排序）

Answer 1

不是，删除特定元素的时间复杂度不是O(1)，有记载是O(N):

官方JavaDocs for PriorityQueue状态：

Implementation note: this implementation provides O(log(n)) time for the enqueuing and dequeuing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

（强调我的）

因此删除具有 remove(Object) 的特定元素具有线性（即 O(N)）时间复杂度。

但是，还有remove()，它总是移除Queue的头部，并且是O(1)。

Oracle OpenJDK reference implementation 使用 indexOf(Object)，这反过来只是对包含元素的内部数组执行线性搜索。

内置的 PriorityQueue remove() 函数如何在 java 中找到要删除的所需元素

how does the inbuilt PriorityQueue remove() function finds the required element to be deleted in java

java

priority-queue

data-structures