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?

Huntress

Did you consider reading the Javadoc? "this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add)". – Clique

Yeah, I did. On the next line it says 'linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size)', which was where I was getting confused. I think I got it now though. – Huntress

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.

Desert

How is removing (a random object in PriorityQueue) taking O(logN) time? In my head, I was thinking something like re-construct the PriorityQueue for the remaining N-1 element, which takes O(NlogN) time in Java, O(N) in theory. Correct me if I am wrong.. – Cranwell

@SeanL, we do not need to reconstruct the heap from nothing. The algorithm for restoring heap property after removing the root works after removing an arbitrary object too. – Breve

Regarding George's comment. The javadoc says that the method remove(Object) takes linear time. > linear time for the remove(Object) and contains(Object) methods; Ref – Trader

docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html linear time for the remove(Object) and contains(Object) methods – Crossly

Answer 2

The complexity for remove is O(N) since the complexity for contains is O(N) (in java's priority queue class)

One way this can be made O(logN) in your own Priority Queue implementation is to maintain an auxiliary data structure like a HashMap that maintains the mappings from a value in the priority queue to its position in the queue. So, at any given time - you would know the index position of any value.

Note that this modification does not affect the running time of any of the existing operations - you would only need to update the mappings during the heapify operations.

Tertiary

So if I know the index position of an element, how do I remove it in Priority Queue API based on the index? (in O(logN) time) – Egocentrism

@Egocentrism Unfortunately, the Java API doesn't expose a way of accessing elements in a priority queue by index, so you'll have to use your own home-built implementation of a priority queue. – Surroundings

How come it's O(logN) to remove from our own implementation and not O(1)? I'm sure I'm missing some detail, but a priority queue is just a data structure sorted from high to low priority. If it's implemented using a linked list, and we know the index, can't we just remove that element and connect the previous node to the following node? – Fermentative

@Fermentative Not sure what you mean by index in a linked list. But if you mean that you are holding an actual pointer to the node you want to remove then, yes, removal is O(1). However, normally you wouldn't use linked list for priority queue because your insert/lookup operations become O(n). While more common implementations (like binary heap for example) of priority queue give you O(log n) for all three: insert/lookup/removal. – Upswell

Yes that is what I mean for the linked list implementation: we have a map of priority value to the index in the queue. Actually removing is O(1), but then I realize that maintaining this map would mean we have to update all the other indexes so that's O(n). – Fermentative

Regarding the mapping and custom implementation you mention, I have seen this done simply by adding an index property to the item class being stored, updated during heapify operations. If the item at index is the item, contains is true and O(1), and remove(item) would be O(log n) worst case. Worked very well for pathfinding. – Supplicate

Answer 3

According to Oracle documentation: "Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing 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)."

Link here to Oracle Doc

Raspy

I think he meant remove(object) not remove() the first is O(n), the latter is O(log n) – Camargo

remove() and poll() are the same except for missing element semantics. Removing a specific item (remove(Object)) is O(n). I think the question wasn't clear and this is a valid answer too... – Someone

Answer 4

Please check: http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

"this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods"

Thus for poll() and remove(), that' log(N) But for remove(object), that log(N)

Crossly