48

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?

samturner
  • 2,213
  • 5
  • 25
  • 31
  • Did you consider reading the Javadoc? ["this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add)"](http://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html). – user207421 Oct 04 '12 at 01:39
  • 7
    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. – samturner Oct 04 '12 at 03:17

4 Answers4

55

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.

GC001
  • 871
  • 8
  • 12
  • 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](https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/). Correct me if I am wrong.. – Sean L Apr 20 '18 at 16:29
  • 6
    @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. – George Leung May 04 '18 at 05:41
  • 3
    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](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html) – deba Jan 31 '21 at 05:29
  • https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html linear time for the remove(Object) and contains(Object) methods – LookIntoEast Aug 08 '21 at 18:29
38

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.

Hari
  • 5,057
  • 9
  • 41
  • 51
  • 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) – novalain Aug 25 '15 at 03:17
  • 3
    @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. – John Kurlak Oct 18 '15 at 18:12
  • 3
    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? – user3125693 Jan 10 '18 at 23:13
  • 2
    @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. – Incassator Jan 19 '18 at 08:52
  • 1
    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). – user3125693 Jan 20 '18 at 16:47
  • 2
    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. – Daniel Nov 17 '18 at 01:04
10

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

Bad Green
  • 121
  • 1
  • 3
  • 3
    I think he meant remove(object) not remove() the first is O(n), the latter is O(log n) – Eran Medan May 21 '16 at 18:40
  • 2
    `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... – TWiStErRob May 23 '16 at 11:36
0

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)

LookIntoEast
  • 8,048
  • 18
  • 64
  • 92