4

Possible Duplicate:
How to sort a Map<Key, Value> on the values in Java?
how to sort Map values by key in Java

I am trying to keep track of scores and I need to be able to sort the scores into non-ascending order without getting the keys and values out of line. My first thought was to use a map but I'm really struggling to find a way to keep a map sorted by value. The values are all Integer objects. How would I go about sorting a high score list like this?

Community
  • 1
  • 1
SaxSalute
  • 349
  • 2
  • 8
  • 1
    This post seems to describe your issue: [http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java][1] [1]: http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java – EdgeCase Jul 14 '12 at 23:39

1 Answers1

1

This is a Microsoft / Amazon job interview type of question. You can use a priority queue, in other to have the highest score as the first element of the queue. Create a node as key | value pair. Implement it in a way the key order is maintained by the score value, and implement the queue.

Giving 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, make the Comparison based on the score value. If you need to search / update, it is O(1), according to the Java API:

Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

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

cybertextron
  • 10,547
  • 28
  • 104
  • 208
  • This is a question about sorting maps. How is a PriorityQueue relevant? – Bohemian Jul 14 '12 at 23:37
  • @Bohemian No, it's not. It's a question about which data structure is best for the job. OP simply explained that he _tried_ with a map, not that he _wants_ a map-based solution. – kba Jul 14 '12 at 23:39
  • I'm a bit confused about how I would use a PriorityQueue in order to sort the Integer values while still maintaining the position of the Strings. – SaxSalute Jul 14 '12 at 23:45
  • Could you write me a small code snippet please? – SaxSalute Jul 14 '12 at 23:58
  • @SaxSalute I gave more details about the implementation. Which programming language are you using? – cybertextron Jul 14 '12 at 23:58
  • @SaxSalute I may give you some code snippet, but I need to know which programming language you're using. – cybertextron Jul 15 '12 at 00:00
  • @SaxSalute I updated my question. I guess you have now all the base you need to get your job done. – cybertextron Jul 15 '12 at 00:18