I have a TreeMap, and want to get a set of K smallest keys (entries) larger than a given value.

I know we can use higherKey(givenValue) get the one key, but then how should I iterate from there?

One possible way is to get a tailMap from the smallest key larger than the given value, but that's an overkill if K is small compared with the map size.

Is there a better way with O(logn K) time complexity?

CodePudding user response：

The error here is thinking that tailMap makes a new map. It doesn't. It gives you a lightweight object that basically just contains a field pointing back to the original map, and the pivot point, that's all it has. Any changes you make to a tailMap map will therefore also affect the underlying map, and any changes made to the underlying map will also affect your tailMap.

for (KeyType key : treeMap.tailMap(pivot).keySet()) {
}

The above IS O(logn) complexity for the tailMap operation, and give that you loop, that adds K to the lot, for a grand total of O(logn K) time complexity, and O(1) space complexity, where N is the size of the map and K is the number of keys that end up being on the selected side of the pivot point (so, worst case, O(nlogn)).

If you want an actual copied-over map, you'd do something like:

TreeMap<KeyType> tm = new TreeMap<KeyType>(original.tailMap(pivot));

Note that this also copies over the used comparator, in case you specified a custom one. That one really is O(logn K) in time complexity (and O(K) in space complexity). Of course, if you loop through this code, it's.. still O(logn K) (because 2K just boils down to K when talking about big-O notation).