CODEWITHSUNDEEP
javasorting
Dev
Dev

Reputation: 13753

Sorting in map on the basis of order of numeric key

I have a Map<String,Map<Integer,String>>

Sample data in this map

("aa" , ((3, "xx"),(5, "yy"),(1,"zz")))

("bb" , (5, "zz"))

Here Integer key of the inner map lies between 1 to 5. It is basically a priority number.

Now I need to fetch value for some key (say aa). It should return values from the inner map with the highest priority number (key).

In above example , yy should be returned.

Note: order of insertion of data in map has nothing to do with order of inner map's key.

What should I do -

Upvotes: 1

Views: 112

Answers (3)

castletheperson
castletheperson

Reputation: 33496

Options 2 & 3 are less efficient, because you will have to sort/iterate every time you poll for a value.

You can implement option #1 with a TreeMap and all the sorting will be handled for you as elements are added. Then use TreeMap#lastEntry() to get the entry with the highest key value.

Using some Java 8 features:

Map<String,TreeMap<Integer,String>> outerMap = new HashMap<>();

public void insert(String outerKey, Integer innerKey, String innerValue) {
    outerMap.computeIfAbsent(outerKey, k -> new TreeMap<>())
        .put(innerKey, innerValue);
}

public String pollHighest(String outerKey) {
    return Optional.of(outerKey)
        .map(outerMap::get)
        .map(TreeMap::lastEntry)
        .map(Map.Entry::getValue)
        .orElse(null);
}

Upvotes: 2

Amber Beriwal
Amber Beriwal

Reputation: 1598

Option #2 will have O(n) complexity in worst case.

Option #3 will need sorting at each and every step. That would be O(n) in worst case, if you insert elements one by one using Insertion sort algorithm.

For internal map, you can use TreeMap. It will keep the data sorted for you. TreeMap guarantees log(n) time complexity for operations. For your case, a priority queue (made using max heap) can also be used.

Upvotes: 1

Nasreen
Nasreen

Reputation: 112

If no other operations are done on this map, them it is better to go with option#1 which builds the map as per the requirement. No need of further iterations over it.

I suggest to use treeMap for the innerMap on the basis of key.

Upvotes: 0

Related Questions