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?

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

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

Solution 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

Comments

[user207421]

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

[samturner]

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.

[novalain]

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)

[SubParProgrammer]

@novalain 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.

[Eran Medan]

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

[TWiStErRob]

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

[user3125693]

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?

[Incassator]

@user3125693 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.

[user3125693]

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

[Sean L]

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

[George Leung]

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

[Daniel]

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.

[deba]

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

[LookIntoEast]

docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.ht‌​ml linear time for the remove(Object) and contains(Object) methods