2

I'm trying to get the top 10 elements of a TreeMap by executing this loop:

        TreeMap<Integer, Integer> sortedMap = sortMap(m);
        String outString = "";
        int count = 10;
        while (count > 0) {
            count--;
            Integer k = sortedMap.firstKey();
            outString += String.valueOf(k);
            sortedMap.remove(k);
            if (count != 0) {
                outString += ",";
            }
        }

        System.out.println("outVal is " + outVal);

This prints outVal is 11377,11377,11377,11377,11377,11377,11377,11377,11377,11377 Integer implements Comparable, so why might remove not be working?

UPDATE Here's my sortMap implementation:

        public static TreeMap<Integer, Integer> sortMap(HashMap<Integer, Integer> map) {
           ValueComparator bvc =  new ValueComparator(map);
           TreeMap<Integer,Integer> sorted_map = new TreeMap<Integer,Integer>(bvc);
           sorted_map.putAll(map);
           return sorted_map;
        }

class ValueComparator implements Comparator<Integer> {
    java.util.Map<Integer, Integer> base;
    public ValueComparator(java.util.Map<Integer, Integer> base) {
        this.base = base;
    }

    // Note: this comparator imposes orderings that are inconsistent with equals.    
    public int compare(Integer a, Integer b) {
        if (base.get(a) >= base.get(b)) {
            return -1;
        } else {
            return 1;
        } // returning 0 would merge keys
    }
}

UPDATE This was helpful: Java Map sort by value.

Community
  • 1
  • 1
Rose Perrone
  • 61,572
  • 58
  • 208
  • 243

3 Answers3

6
public int compare(Integer a, Integer b) {
    if (base.get(a) >= base.get(b)) {
        return -1;
    } else {
        return 1;
    } // returning 0 would merge keys
}

This comparator is flawed as (quite apart from it being inconsistent with equals) it does not satisfy the comparator contract which states that compare(a,b) > 0 implies compare(b,a) < 0 and vice versa. And since TreeMap relies on the comparator returning 0 to find the key you're trying to remove() it will never be able to remove anything - no matter what key you try and search for the map will never think that the key is present.

Ian Roberts
  • 120,891
  • 16
  • 170
  • 183
  • This is why this approach to sorting a `Map` is pretty inevitably doomed to failure. Use an approach like http://stackoverflow.com/a/2581754/869736 . – Louis Wasserman Jan 14 '14 at 17:38
4

After your edit it is clear that your custom comparator is the culprit. What you actually want to achieve is collecting the keys of the ten highest values in the map.

But, your approach is needlessly roundabout, if I may say. You already have some map m, which is your starting point. So what you need is just collect its entrySet, sort it by value, and take the first ten elements:

import java.util.Map.Entry;

final List<Entry<Integer,Integer>> list = new ArrayList<>(m.entrySet());
Collections.sort(list, new Comparator<Entry<Integer, Integer>>() {
  @Override public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
    return o1.getValue().compareTo(o2.getValue());
  }});
final StringBuilder b = new StringBuilder();
String delimiter = "";
for (Entry<Integer, Integer> e : list.subList(0, 10)) {
  b.append(delimiter).append(e.getKey());
  delimiter = ",";
}
System.out.println(b);

Note that a one-shot sort is more efficient than inserting elements one by one into a binary search tree.

I am also using StringBuilder, which is again more efficient than recreating a full String in each step.

Marko Topolnik
  • 195,646
  • 29
  • 319
  • 436
  • You don't need to sort at all - [new ArrayList(Collection)](http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html#ArrayList%28java.util.Collection%29) states *Constructs a list containing the elements of the specified collection,* **in the order they are returned by the collection's iterator.** – OldCurmudgeon Jan 14 '14 at 17:06
  • @OldCurmudgeon which is fine if the _original_ `m` is already a `SortedMap`, but that is not clear from the question. – Ian Roberts Jan 14 '14 at 17:09
  • 1
    And you could use `for(int k : list.subList(0, limit))` and get rid of the `if`. – Alexis C. Jan 14 '14 at 17:33
0

i tried like following it worked for me

    TreeMap<Integer, Integer> sortedMap = new TreeMap<>();
    String outString = "";
    sortedMap.put(1, 10);
    sortedMap.put(2, 20);
    sortedMap.put(3, 30);
    sortedMap.put(4, 40);
    sortedMap.put(5, 50);
    int count = 5;
    while (count > 0) {
        count--;
        Integer k = sortedMap.firstKey();
        outString += sortedMap.get(k);//String.valueOf(k);
        sortedMap.remove(k);
        if (count != 0) {
            outString += ",";
        }
    }

    System.out.println("outVal is " + outString);
    System.out.println(sortedMap.size());
Muhammad
  • 6,725
  • 5
  • 47
  • 54