TreeMap: get values in sorted order

Question

i have the following TreeMap:

TreeMap<Integer, Double> map;

the Double values are not unique.

i iterate through the map using Integer keys and the functions firstEntry() and higherEntry() and modify the Double values.

Now i want to list the values of the pairs in the order of decreasing Double values. what is the best way to do this?

those Integer keys are important to me and because the Double values are not unique, i cannot have a Double key.

Update: More Explanation it is the classic problem. lets say rollnos of students is the key and their percentage is the value. now sort by percentage and then we should be able to tell whose percentage is it. therefore i need the integer key.

Answer 1

What you can do is the following : use entrySet to iterate through the entries. Put them into a list. Sort the date with the right comparator then.

Answer 2

The obvious solution is to obtain a collection of the doubles (possibly via the entrySet and then getValue - the TreeMap class has a values() method, you can just use that), and proceed to sort them (using Collections.sort or Arrays.sort) - this would, however, take O(n logn) time.

I'm not sure you can do it in a smarter (== faster) way, unless you completely change the data structure. However, the only way in which I see this happening with another data structure is keeping a wrapper over the integer and the double and writing two comparators - one which compares the integer and one which compares first by the double and then by the integer. The original TreeMap you're using would be the same but you would be able to detach another TreeMap from it, sorted by the second comparator. Detaching would still take O(n logn) time though.

Answer 3

you can build a TreeSet, that guarantees insertion order:

@Test
public void treeMapSortedByValue() {
    // given the following map:
    TreeMap<Integer, Double> map = new TreeMap<Integer, Double>();
    map.put(2, Math.E);
    map.put(1, Math.PI);
    map.put(3, 42.0);

    // build a TreeSet of entries
    Set<Map.Entry<Integer, Double>> sortedEntries = new TreeSet<Map.Entry<Integer, Double>>(new DoubleComparator());
    sortedEntries.addAll(map.entrySet());

    // optionally you can build a List<Double> with the sorted 
    List<Double> doubles = new LinkedList<Double>();
    for (Map.Entry<Integer, Double> entry : sortedEntries) {
        doubles.add(entry.getValue());
    }
}

this should give you: [2.718281828459045, 3.141592653589793, 42.0] (nb: [Math.E, Math.PI, Math.UNIVERSAL_ANSWER] :-).

PS

the Comparator:

class DoubleComparator implements Comparator<Map.Entry<Integer, Double>> {

    @Override
    public int compare(Entry<Integer, Double> o1, Entry<Integer, Double> o2) {
        return Double.compare(o1.getValue(), o2.getValue());
    }
}