Geek Answers Handbook

Looking for an indexable data structure for sorting with multiple keys

I want to save pairs <Integer, Object>and keep them in ascending order with the whole key. However, it should be allowed to store the same key for different objects in the structure, so I cannot use one of the standard cards.

In addition, pairs must be inverted by the index. Therefore, if I want to refer to a pair with index 2 (the third largest integer value), it must return the object stored there. Subsequently, I want to change the integer value, sort the structure back, and change the indexes in order of increasing order.

The number of pairs in this structure will be constant, so I do not need efficient insertion or deletion, only efficient sorting.

Is there such a data structure in Java (or at least in general)?

+4
source share
2 answers

If you intend to use the same key for multiple entries, you should, for example, use MultiMapfrom Google Guava.

http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html

One of the implementations of the interface MultiMapis SortedSetMultimap, which can be very useful in your case.

0
source

, , , - (.. (BST), node , node).

( , ) , BST, .

i- , , node , .

O (log n).

order - (, ) . , , node (, List) , (.. node) .

. , - , .

:

O (n) i- O (log n) , , , , TreeMap<Integer, List<Object>> ( Guava MultiMap), .. node . , i- , , .

O (1), i- , O (n) , ArrayList , . , O (n).

0

More articles:


All Articles