Collections: PriorityQueue.remove(Object) is O(n) despite the heap

Removing the head of a PriorityQueue is O(log n), but remove(Object) has to scan the backing array linearly to find a match before it can repair the heap, so it costs O(n).

Code

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 4, 2, 3));
System.out.println("Heap array order: " + pq);
boolean removed = pq.remove(4);
System.out.println("Removed 4 by linear scan? " + removed);
System.out.println("Heap after removal: " + pq);
System.out.println("Still a valid heap, peek: " + pq.peek());

Output

Heap array order: [1, 2, 4, 5, 3]
Removed 4 by linear scan? true
Heap after removal: [1, 2, 3, 5]
Still a valid heap, peek: 1