Java structure suggestion for a sorted list of pairs with unique keys

Question

A structure k => v (k and v are >=0 ints) where all k are unique while v may be equal (k1 => v and k2 => v) should be sorted in ascending order of v values, for example:

Let we have [35 => 1, 23 => 4, 9 => 9, 2 => 14] and want to insert a new pair 20 => 5, then the result is going to be [35 => 1, 23 => 4, 20 => 5, 9 => 9, 2 => 14].

What is the fastest structure in Java I can use in order to create it based on some input data and further iterate it in a 'one-by-one' fashion from the left. SortedHashMap?

TreeMap (the concrete implementation of SortedMap) sorts the keys, not the values, by default. [This is one possible approach](http://stackoverflow.com/a/11504977/829571). — assylias, Aug 15 '12 at 09:50
The keys are unique and should not be sorted, but values should. — Sophie Sperner, Aug 15 '12 at 09:51
@Sopie Yes which is why you can't use a TreeMap as is (is sorts the keys). The link I posted gives an example to sort by values. — assylias, Aug 15 '12 at 09:52
Do you need a data structure that can be built incrementally, or is it ok to collect all pairs, and then build the structure? — meriton, Aug 15 '12 at 09:56
possible duplicate of [How to sort a Map on the values in Java?](http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java) — Jim, Aug 15 '12 at 10:01
You could use [TreeMap](http://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html) for sorted Keys; **EDIT** but for sorted values you need to take some [custom](http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java) approach. — Bharat Sinha, Aug 15 '12 at 09:51
Thanks. I did not see that the users asked for sorted values. — Bharat Sinha, Aug 15 '12 at 09:53

score 1 · Answer 1 · answered Aug 15 '12 at 10:00

I don't think that there is an existing structure for that.

A SortedMap is not the right thing for you because it sorts using the keys and not the values.

I would use a HashMap and implement the sorting in an additional method which copies the entrySet into a list. The list would be sorted using a custom comparator which compares the values.

If performance is a big big point here you should think about implementing an own structure. There are many possibilities to do this and one cannot say what is the fastest. It depends on what operations you want to execute how often.

thkala · Accepted Answer · 2012-08-15T10:20:43.847

1

Some time ago I encountered a similar situation; I used a couple of maps in parallel:

A HashMap<K, P> M, where P is the pair type, to be able to find pairs by their key.
A TreeMap<P, P> S, with a comparator that sorts first by the value and then by the key, to always have the correct sorting order available.

By maintaining both structures in parallel, it is possible to always have your pairs sorted, without having to use the key as the sorting value.

To add a pair:

M.put(key, pair);
S.put(pair, pair);

To get a pair by key:

M.get(key);

To remove a pair:

P pair = M.get(key);
M.remove(key);
S.remove(pair);

To get a sorted list of pairs:

S.keySet();

The average complexity of the core operations is:

Add: O(logn) (TreeMap)
Get: O(1) (HashMap)
Remove: O(logn) (TreeMap)

edited Aug 15 '12 at 10:20

answered Aug 15 '12 at 10:09

thkala

84,049
23
157
201

+1: Nice idea with the composite comparator :-) Since the second map is only used for iteration, wouldn't it be easier to use a TreeSet for that? – meriton Aug 15 '12 at 10:25
@meriton: `TreeSet` is just a wrapper around `TreeMap`. I prefer using TreeMap because of the operation uniformity with `HashMap` and the better future extensibility. It also saves an object per instance :-D – thkala Aug 15 '12 at 10:38
I did something like you suggested. – Sophie Sperner Aug 15 '12 at 18:19

score 1 · Answer 3 · answered Aug 15 '12 at 10:10

If you don't need incremental construction, I'd do:

List<Pair> pairs = ...;
Collections.sort(pairs, new Comparator<Pair>() {
    @Override public int compare(Pair p1, Pair p2) {
        return p1.v - p2.v;
    }
}
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
map.addAll(pairs); // retains insertion order
return map;

Java structure suggestion for a sorted list of pairs with unique keys

3 Answers3