What data structure should be used to list high scores?

Question

Possible duplicate:
How to sort a <Key, Value> map about values ​​in Java?


how to sort map values ​​by keywords in java

I am trying to track grades, and I need to be able to sort grades in non-increasing order without getting keys and values ​​out of line. My first thought was to use a map, but I'm really trying to find a way to keep the map sorted by value. Values ​​are whole objects. How can I sort a high-ranking list like this?

Answer 1

This is a type of interview with Microsoft / Amazon. You can use the priority order, in the other - to have the highest score as the first element of the queue. Create a node pair as key | value key | value . Implement it in such a way that the order of the keys is supported by the evaluation value and implements the queue.

---

Providing more details

---

This is your Node implementation:

 public class Node{ private String name; // the name private double score; // assuming you're using double public Node(String name, double score){ this.name = name; this.score = score; // assuming negative scores are allowed } public void updateScore(double score){ this.score += score; } } 

And when you use PriorityQueue , do Comparison based on the value of the estimate. If you need to search / update, this is O (1), according to the Java API :

Implementation note: this implementation provides O (log (n)) time for input and delete methods (suggestion, poll, delete () and add); linear time to delete (Object) and contains (Object) methods; as well as constant time for search methods (peek, element and size).

Read the API, I think you probably need to rewrite Comparator<? super E> comparator() Comparator<? super E> comparator() or at least change it for your needs. That should do it.