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

Question

the remove method :-
public remove(): This method removes a single instance of the specified element from this queue, if it is present

does the remove method work in O(1) ? if so

how does it find the specific element

as priority queue uses array and it is not sorted therefor we cannot use binary search and linear search is a costly operation.

how does it work?

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");

how does the remove method find "To" in the priorityqueue array {"Overflow","Welcome","To"} (not in sorted form)

Answer 1

No, the time complexity for removing a specific element is not O(1), it is documented to be O(N):

The official JavaDocs for PriorityQueue state:

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).

(emphasis mine)

So removal of a specific element with remove(Object) has linear (i.e. O(N)) time complexity.

However, there is also remove(), which always removes the head of the Queue, and is O(1).

The Oracle OpenJDK reference implementation uses indexOf(Object), which in turn just performs a linear search over the internal array holding the elements.