AddInOrder Best Structure? Java homework

Question

Hi

Currently I have a problem where I have a list of IDs, each with a related score.

For example:

ID : SCORE

1 : 12

2 : 15

3 : 2

4 : 99

I want to loop over these and add them to a structure in decending order of score. So the output will look something like

{4,2,1,3}

What is the best way of doing this in Java? A queue?

Thanks Philip

Answer 1

Isn't Collection.sort(list, comparator) appropriate?

(comparator is a class implementing Comparator and specifying the comparison logic)

(alternatively, your class may implement the Comparable interface to provide the comparison logic internally)

It is not "AddInOrder", but it fulfills your requirement.

Answer 2

There are multiple options here. Sorting the list at the end might suffice for your purposes.

If you want to ensure that the order invariant holds all the time, then a sorted list/tree is the way to go. Java provides a PriorityQueue class.

However, as an implementation detail, you would need to create a class to encapsulate both the ID and the Score, and have the class be comparable with respect to your particular sorting choice.

Answer 3

Insert the items one by one into a sorted set (like a tree set). Use a class to hold id:score, and write a comparator which compares two instances of this classes based on their score.

EDIT: Saw that you already have the list, in this case sorting the collection is better.

Answer 4

I think this is a great time to learn the Comparable interface. You could make a Class that compares by score and prints its id when toString() is called. As mentioned earlier, using a custom Comparator would also suffice, but if you've never worked with Comparable I recommend learning that first.

Here's a link to the JavaDoc: http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Comparable.html

You should know that for two objects o1 and o2 of type Comparable<T>, o1.compareTo(o2) will return:

• -1 if o1 < o2 (in the ordering defined by T, the type of o1 and o2)
• 0 if o1 == o2 (again, in the ordering, not necessarily object equality)
• 1 if o1 > o2

This information will help you write your compareTo function in your custom class.

Once you have your class written, then Java's Collections class provides a sort method that will sort a List of Comparables. Easy!

Here's the link for that: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Collections.html#sort%28java.util.List%29