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?
-
Did you consider reading the Javadoc? "this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add)".user207421– user2074212012-10-04 01:39:31 +00:00Commented Oct 4, 2012 at 1:39
-
7Yeah, 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.samturner– samturner2012-10-04 03:17:14 +00:00Commented Oct 4, 2012 at 3:17
Add a comment
|
4 Answers
The confusion is actually caused by your "remove" function. In java, there are two remove functions.
remove() -> This is to remove the head/root, it takes O(logN) time.
remove(Object o) -> This is to remove an arbitrary object. Finding this object takes O(N) time, and removing it takes O(logN) time.
4 Comments
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.
LookIntoEast
docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html linear time for the remove(Object) and contains(Object) methods
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.
6 Comments
John Kurlak
@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.
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).
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.
|
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)."
2 Comments
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...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)
