java - Java 的 TreeMap 中的关键更新

Question

是否有机会一次更新 TreeMap 中最少键条目 (firstEntry()) 的键？因此，例如，如果我 pollFirstEntry()，则检索和删除条目需要 O(log n) 时间。之后，我用所需的键创建一个新条目并将其放回 TreeMap，这也需要 O(log n) 时间。因此，我花费了 O(2 log n) 时间，在逻辑上可能只是 O(1+log n) = (log n) 时间的情况下。

我很乐意避免删除该条目，但会在它被 firstEntry() 方法捕获时更新它。如果使用 TreeMap 不可能，有人可以建议替代 PriorityQueue 之类的数据结构，在可能的情况下更新最少条目的键。

Answer 1

O(2 log N) 被正确地认为是 O(log N)。但是不，不能这样做，因为 map 中的条目更改为另一个位置(在树中)。几乎唯一不成立的数据结构是键值对列表，这是一个糟糕的 O(N) 或者你可能喜欢的 O(N/2).

如果键可以用作一个巨大数组中的索引，那么 O(1) 将成立，仍然是 2 个操作。