0

the remove method :-
public remove(): This method removes a single instance of the specified element from this queue, if it is present

does the remove method work in O(1) ? if so

how does it find the specific element

as priority queue uses array and it is not sorted therefor we cannot use binary search and linear search is a costly operation.

how does it work?

PriorityQueue<String> queue = new PriorityQueue<String>(); 

// Use add() method to add elements into the Queue 
queue.add("Welcome"); 
queue.add("To"); 
queue.add("Overflow"); 

queue.remove("To");

how does the remove method find "To" in the priorityqueue array {"Overflow","Welcome","To"} (not in sorted form)

Arjun S D-16
  • 15
  • 5
  • Its used the equals and hashCode methods of the String class to compare what you give it and find if something matches it. Normaly just hashcode is enough, but sometimes, mostly with strings they can collide on their hash value, so equals is also needed to find the correct value. EDIT: Looked at the code, seems PriorityQueue just uses equals. – MissingSemiColon Jul 08 '20 at 08:04

1 Answers1

1

No, the time complexity for removing a specific element is not O(1), it is documented to be O(N):

The official JavaDocs for PriorityQueue state:

Implementation note: this implementation provides O(log(n)) time for the enqueuing and dequeuing 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).

(emphasis mine)

So removal of a specific element with remove(Object) has linear (i.e. O(N)) time complexity.

However, there is also remove(), which always removes the head of the Queue, and is O(1).

The Oracle OpenJDK reference implementation uses indexOf(Object), which in turn just performs a linear search over the internal array holding the elements.

Hulk
  • 6,399
  • 1
  • 30
  • 52
  • i want to know how it is implemented to make the find function linear – Arjun S D-16 Jul 08 '20 at 08:04
  • It searches the entire queue and performs an equals comparation on each element of the queue. If found it stops the search, it then as to move the elements based on where the element was found. Its linear beacuse it will start from the begining and move forward till it finds it, so more elements = more search time. – MissingSemiColon Jul 08 '20 at 08:11
  • @MissingSemiColon then it is not a constant time function but in the documentation it states that it is a constant time function – Arjun S D-16 Jul 08 '20 at 10:06
  • where does it say that? It clearly states its linear time... https://en.wikipedia.org/wiki/Time_complexity#Linear_time. @Hulk already pasted the link to the documentation for PriorityQueue – MissingSemiColon Jul 08 '20 at 11:23
  • ya did not read it properly, it a linear time method – Arjun S D-16 Jul 09 '20 at 13:04