Java, how to sort char alphabetically in Comparator

Question

I am trying to built a maxheap of characters. First sort by frequency, if frequency is same, then sort alphabetically.

Map<Character, Integer> map = new HashMap<>();
for(int i = 0; i < n; i++) {
     char c = s.charAt(i);
     map.put(c, map.getOrDefault(c, 0) + 1);
}

Queue<Character> pq = new PriorityQueue<>(new Comparator<Character>(){
  @Override
  public int compare(Character c1, Character c2){
   if(map.get(c1) == map.get(c2)){
     return c1 < c2 ? -1 : (c1 == c2 ? 0 : 1);
     //return (char)c1 - (char)c2; same output
   }
   return map.get(c2) - map.get(c1);
  }
});

for(char key : map.keySet()){
   pq.offer(key);
   System.out.println(key + " has freq " + map.get(key));
}

while(!pq.isEmpty()) {
     System.out.print(pq.poll() + " ");
}

I put 26 letters into this maxheap, and each letter has same frequency 5000.

But the output order is 'a', 'z', 'y', 'x'...., 'c', 'b'.

when frequency of each char is 5, the order is correct.

I don't understand why the output with frequency 5000 is like this. How can I get a right order?

When your Integers are 5000, they are all different objects, so map.get(c1) == map.get(c2) is false. When they are 5, they are all the same object due to a optimization in Java, and in that case map.get(c1) == map.get(c2) is true. — Matt Timmermans
– Matt Timmermans, Commented Sep 24, 2019 at 2:44

OneCricketeer · Accepted Answer · 2019-09-24 02:38:02Z

3

Given that all frequencies are the same, your if statement is wrong. You could use built-in methods to compare the objects and return the results

Integer f1 = map.get(c1);
Integer f2 = map.get(c2);
int x = f1.compareTo(f2)
if(x == 0){
    return Character.compare(c1, c2);
}
return x;

answered Sep 24, 2019 at 2:38

OneCricketeer

193k20 gold badges146 silver badges276 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Holger · Accepted Answer · 2019-10-01 17:22:20Z

You are comparing two Integer instances via == with the if(map.get(c1) == map.get(c2)) statement. The reason why it works when the frequency is five, is that there is a mandatory caching for autoboxing values in the -128…+127 range. When the frequency is 5000, the identity of the Integer objects is unspecified and equal objects may have different identities.

One fix would be to use equals instead. The other is to stop implementing Comparator manually and use the factory methods. Together with other improvements, your code simplifies to

Map<Character, Integer> map = new HashMap<>();
for(int i = 0; i < n; i++) {
     map.merge(s.charAt(i), 1, Integer::sum);
}

Queue<Character> pq = new PriorityQueue<>(
    Comparator.<Character>comparingInt(map::get).reversed()
        .thenComparing(Comparator.naturalOrder())
);

map.forEach((key, freq) -> {
   pq.offer(key);
   System.out.println(key + " has freq " + freq);
});

while(!pq.isEmpty()) {
     System.out.print(pq.poll() + " ");
}

Muzamil Mehmood · Accepted Answer · 2019-09-24 02:35:21Z

0

you can compare two objects with .equals() method. it will return a Boolean value. if you want to hard code comparison then assign a integer value to each alphabet(total 26 variables) and compare their integer value and you'll know which one to place where.

answered Sep 24, 2019 at 2:35

Muzamil Mehmood

447 bronze badges

Collectives™ on Stack Overflow

Java, how to sort char alphabetically in Comparator

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related