Efficient way to find min value in Map

Question

I am trying to find key with minimum value in Map shown below.

 Map<Node, Integer> freeMap = new TreeMap<>();
 Node minNode = null;
        for (Map.Entry<Node, Integer> entry : freeMap.entrySet()) {
            if (minNode == null) {
                minNode = entry.getKey();
            } else {
                if (entry.getValue() < freeMap.get(minNode)) {
                    minNode = entry.getKey();
                }
            }
        }

Firstly, Is there a straight forward way to find key with minimum value than using foreach loop. Secondly, can you suggest some alternate data structure approach which can be used to store a Node object and an associated Integer value, so I can fetch entry with minimum value in constant time O(1).

Answer 1

If your goal is to improve time complexity, there's really only one possible change, from O(n log n) to O(n):

 Map<Node, Integer> freeMap = new TreeMap<>();
 Map.Entry<Node, Integer> minEntry = null;
 for (Map.Entry<Node, Integer> entry : freeMap.entrySet()) {
   if (minEntry == null || entry.getValue() < minEntry.getValue()) {
      minEntry = entry;
   }
 }
 Node minNode = minEntry.getKey();