0

I have a problem about PriorityQueue.

   public static void main(String[] args) {
        sortByBits(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8});
        System.out.println(1);
    }

    public static int[] sortByBits(int[] arr) {
        Map<Integer, Integer> m = new HashMap<>();
        PriorityQueue<Integer> p = new PriorityQueue<>((a, b) -> {
            if (m.get(a) == m.get(b)) {
                return a - b;
            } else {
                return m.get(a) - m.get(b);
            }
        });
        for (int i = 0; i < arr.length; i++) {
            m.put(arr[i], Integer.bitCount(arr[i]));
            p.offer(arr[i]);
        }
        int[] result = new int[p.size()];
        int size = p.size();
        for (int i = 0; i < size; i++) {
            result[i] = p.poll();
        }
        return result;
    }

Map m is
0 -> 0,
1 -> 1,
2 -> 1,
3 -> 2,
4 -> 1,
5 -> 2,
6 -> 2,
7 -> 3,
8 -> 1,
I wanna sorted by map's value in PriorityQueue, expected result is 0-1-2-4-8-3-5-6-7 or others right , but now is 0-1-2-8-4-5-6-7-3, it's obvious that key 7's value is 3,the biggest, should at the end...but now the end is 3, I don't know why.
Thanks you.

Rock Lee
  • 1
  • 1
  • 1
    Welcome to Stack Overflow. Could you provide a [mcve]? In particular, if the bug is in `calCount`, we could end up spending quite a long time trying to diagnose a problem which isn't in the code you've shown. – Jon Skeet May 05 '20 at 07:51
  • post calCount() code – Dipankar Baghel May 05 '20 at 07:52
  • 1
    This would only count the 1's in the code. See that link I recommended in the answer for a potential solution, there are a few other submissions there as well. – fpezzini May 05 '20 at 08:00
  • 1
    Please edit the code *into the question*. Ideally, it should be a complete example that we can copy, paste, compile and run with no further modification required. – Jon Skeet May 05 '20 at 08:09
  • 1
    How did you find out about the order (0-1-2-8-4-5-6-7-3)? If it is by iterating over the PQ: this is expected. The [documentation](https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#iterator()) says: "The iterator does not return the elements in any particular order" – Thomas Kläger May 05 '20 at 08:14
  • @ThomasKläger Thank you , i have solved my problem.you give me my inspiration. the result is not equal to the Iterator.Thanks.I don't know how to accept your answer, i am new in stackoverflow. – Rock Lee May 05 '20 at 08:43
  • 1
    Since you are putting all elements into the map anyway, there is no need for a fallback in the comparator. `new PriorityQueue<>(Comparator.comparing(m::get))` would work. But I’d avoid mixing modifications of the comparator’s underlying map with populating the queue. While it works here, two loops would be cleaner: `for(int i: arr) m.put(i, Integer.bitCount(i));` `for(int i: arr) p.offer(i);` On the other hand, you don’t need the map at all; you could simply use `PriorityQueue p = new PriorityQueue<>(Comparator.comparingInt( Integer::bitCount)); for(int i: arr) p.offer(i);`. – Holger May 05 '20 at 12:10

1 Answers1

0

PriorityQueue will sort items by the natural order. Since they are integers they will be sorted by ascending order. See here for how to sort the way you need.

fpezzini
  • 774
  • 1
  • 8
  • 17