java - Priority Queue remove complexity time

Question

What is the complexity (big-oh) for the remove() function on the Priority Queue class in Java? I can't find anything documented anywhere, I think it's O(n), considering you have to find the element before you remove it and then reshuffle the tree. but I've seen others that disagree and think it's O(logn). Any ideas?

question from:https://stackoverflow.com/questions/12719066/priority-queue-remove-complexity-time

Answer 1

The confusion is actually caused by your "remove" function. In java, there are two remove functions.

1. remove() -> This is to remove the head/root, it takes O(logN) time.

2. remove(Object o) -> This is to remove an arbitrary object. Finding this object takes O(N) time, and removing it takes O(logN) time.