2

Is there any chance to update a key of the least key entry (firstEntry()) in the TreeMap in one pass? So, for example, if I pollFirstEntry(), it takes O(log n) time to retrieve and remove an entry. Afterwards, I create a new entry with desired key and put it back into TreeMap, it also takes O(log n) time. Consequently, I spend O(2 log n) time, in the case where it is logically could be just O(1+log n) = (log n) time.

I would be very happy to avoid removing the entry, but update it while it captured by firstEntry() method. If it is not possible with TreeMap, could anybody suggest an alternative PriorityQueue like data structure, where possible to update keys of the least entry.

univarn
  • 45
  • 6
  • 1
    Do you actually have a performance problem which would be solved by this, or do you perceive it to be a bit inefficient? – Andy Turner Sep 09 '15 at 17:02
  • I'm just trying to figure out how experienced guys overcome the situation with lack of updateLeastEntryKey() method. And I think that spending logarithmic time instead of constant shall be avoided. – univarn Sep 09 '15 at 17:08
  • It sounds like you are using this like a priority queue. See also http://stackoverflow.com/q/1871253/3788176 – Andy Turner Sep 09 '15 at 17:16
  • "Experienced guys," as you put it, pay attention to the line in the [Map javadoc](http://docs.oracle.com/javase/7/docs/api/java/util/Map.html): "Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map." – Louis Wasserman Sep 09 '15 at 17:42
  • Updating the attributes of an object that define if it's *equal* to another object of the same class is not supported by any structure of the Java Collections framework. Same applies for `hashCode()`, btw. What's wrong with `O(2 log n)` time? It's an excellent trade-off, imho. – fps Sep 09 '15 at 18:48

1 Answers1

1

O(2 log N) is rightly considered O(log N). But no, cannot be done as in the entry in the map changes to another position (in the tree). The almost only data structure where this does not hold is a list of key-value pairs, and that is a terrible O(N) or as you might like O(N/2).

If the key can be used as index in a huge array, then O(1) would hold, still 2 operations.

Joop Eggen
  • 107,315
  • 7
  • 83
  • 138