Priority Queue remove complexity time

java complexity-theory time-complexity priority-queue
samturner picture samturner · Oct 4, 2012 · Viewed 38.6k times · Source

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?

Answer

Chen picture Chen · Aug 23, 2016

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.

Related questions

What is the complexity of this simple piece of code?

I'm pasting this text from an ebook I have. It says the complexity if O(n2) and also gives an explanation for it, but I fail to see how. Question: What is the running time of this code? public String …

Read More
HashMap get/put complexity

We are used to saying that HashMap get/put operations are O(1). However it depends on the hash implementation. The default object hash is actually the internal address in the JVM heap. Are we sure it is good enough to …

Read More
Example of O(n!)?

What is an example (in code) of a O(n!) function? It should take appropriate number of operations to run in reference to n; that is, I'm asking about time complexity.

Read More