CODEWITHSUNDEEP
javaperformancetreemap
zvisofer
zvisofer

Reputation: 1368

Java TreeMap get Kth smallest key

I am using a TreeMap and want to get the Kth smallest key. I wrote the following implementation:

public static Long kthKey(TreeMap<Long, MyObject> treeMap, int kth) {
    Long currentKey = treeMap.firstKey();
    for (int i = 1; i < kth; i++) {
        currentKey = treeMap.higherKey(currentKey);
    }
    return currentKey;
}

This is pretty efficient in terms of memory, but maybe not in terms of running time.

Is there a more efficient way to do this?

Upvotes: 1

Views: 1148

Answers (1)

Peter Lawrey
Peter Lawrey

Reputation: 533510

If you are allowed to use an iterator, you can do this.

public <T> static Long kthKey(Map<T, ?> map, int kth) {
    for(T key: map.keySet())
       if(kth-- < 1) return key;
    return null;
}

The cost of one iterator is not so high, and if you need to avoid this I would suggest looking at how this method is called and optimising that e.g. say you have

for (int k = 0; k < mapsize(); k++) {
    Long l = kthKey(map, k);

You can eliminate the need to call this method at all.

Upvotes: 2

Related Questions