Most frequent word in an array of strings - Java
As you noticed, searching for your entries is adding to your time complexity, because you have to run down your queue. Priority queues are very good at polling the top element, but not optimized for searching for specific entries.

You can optimize for searching by using a Map&lt;String, Integer&gt; for counting frequency, and then use a NavigableMap&lt;Integer, Set&lt;String&gt;&gt; for maintaining order (1). Adding an entry will look like this:

NavigableMap&lt;Integer, Set&lt;String&gt;&gt; ordered;
Map&lt;String, Integer&gt; frequency;

void add(String word) {
  int count = frequency.getOrDefault(word, 0);
  if ( count &gt; 0 ) {
    ordered.get(count).remove(word);
  }
  ordered.computeIfAbsent(count + 1, HashSet::new).add(word);
  frequency.put(word, count + 1);
}


(1) If you're confident about your data being densely distributed and bounded, you can replace this with an array for quicker access—approaching O(1) i.o. O(log N)—but it's going to make your code messier dealing with edge cases.



I do have two recommendations for your code.

When searching for an element in the queue, you can abort once it's found. On average, this will halve your time spent searching:

Iterator&lt;MyWord&gt; itr = queue.iterator();
while (itr.hasNext()) {
   MyWord next = itr.next();
   if (next.getWord().equals(word)) {
       oldWord = next;
       break;  // &lt;-- found, abort search
   }
}


And a nitpick from an 'elegance' point of view: consider adding a method to MyWord that creates a new, incremented instance. Right now, outside code is accessing the fields and creating new instances with it. This is something MyWord can handle internally.

public MyWord incremented() {
    return new MyWord(count + 1, word);
}