CODEWITHSUNDEEP
javadata-structurespriority-queuetreemapred-black-tree
univarn
univarn

Reputation: 45

Key update in Java’s TreeMap

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.

Upvotes: 2

Views: 580

Answers (1)

Joop Eggen
Joop Eggen

Reputation: 109593

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.

Upvotes: 1

Related Questions