Java PriorityQueue not polling in descending order

Can anyone explain to me why this outputs [accountB(200), accountC(200), accountA(200)] instead of [accountA(200), accountB(200), accountC(200)]?

public static void main(String[] args) {
    Map<String, Integer> map = new HashMap<>();
    map.put("accountB", 200);
    map.put("accountA", 200);
    map.put("accountC", 200);
    System.out.println(getTopSpenders(map, 5));
}

static public List<String> getTopSpenders(Map<String,Integer> map, int n) {
    PriorityQueue<Map.Entry<String, Integer>> maxHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
        @Override
        public int compare(Map.Entry<String, Integer> a, Map.Entry<String, Integer> b) {
            if (a.getValue() != b.getValue()) {
                return Integer.compare(b.getValue(), a.getValue());
            }
            return a.getKey().compareTo(b.getKey());
        }
    });

    for (var entry : map.entrySet()) {
        maxHeap.offer(entry);
    }

    List<String> topSpenders = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (maxHeap.isEmpty()) {
            break;
        }

        var spender = maxHeap.poll();
        String sb = spender.getKey() + "(" + spender.getValue() + ")";
        topSpenders.add(sb);
    }

    return topSpenders;
}

Solution

Your comparator always returns 0

As @pebble unit points out in the first comment, using != for comparing your Integer objects is incorrect. It trickingly compares object references, not values. For demonstration I am comparing every entry in your map to every entry using a copy of your Comparator:

public static final Comparator<Map.Entry<String, Integer>> ENTRY_COMPARATOR = (a, b) -> {
    if (a.getValue() != b.getValue()) {
        return Integer.compare(b.getValue(), a.getValue());
    }
    return a.getKey().compareTo(b.getKey());
};

// ...

    for (Map.Entry<String, Integer> leftEntry : map.entrySet()) {
        for (Map.Entry<String, Integer> rightEntry : map.entrySet()) {
            System.out.println(leftEntry.getKey() + " " + rightEntry.getKey() + " " + leftEntry.getValue()
                    + " " + rightEntry.getValue() + " -> " + ENTRY_COMPARATOR.compare(leftEntry, rightEntry));
        }
    }

Output is:

accountB accountB 200 200 -> 0
accountB accountA 200 200 -> 0
accountB accountC 200 200 -> 0
accountA accountB 200 200 -> 0
accountA accountA 200 200 -> 0
accountA accountC 200 200 -> 0
accountC accountB 200 200 -> 0
accountC accountA 200 200 -> 0
accountC accountC 200 200 -> 0

How come? Your value, 200, is outside the range where Java caches and reuses Integer objects (default up to 128, configurable). Therefore autoboxing gives you 3 different Integer objects all having the value 200 for your map. So != yields false and your comparator returns the result of Integer.compare(b.getValue(), a.getValue()). Which is 0 since the values are the same. So the entries are considered equal under your comparator.

What your priority queue does with elements that are considered equal is not specified. Which is why you get the elements in an order that would appear to be random yet reproducible.

The results I got

For documentation, from your code I got:

[accountB(200), accountC(200), accountA(200)]

I ran the code multiple times and always got this order.

The good comparator

The standard library has got some nifty methods for building our comparators for us.

    PriorityQueue<Map.Entry<String, Integer>> maxHeap
            = new PriorityQueue<>(Map.Entry.<String, Integer>comparingByValue()
                    .reversed()
                    .thenComparing(Map.Entry::getKey));

Now the output is what I think you had desired:

[accountA(200), accountB(200), accountC(200)]

Map.Entry has methods comparingByKey and comparingByValue that offer comparators that compare keys and values respectively. Since I read from your code that you want the values in descending order, I reversed() the comparator from comparingByValue(). Comparator.thenComparing is the standard way to chain comparisons so that if the first comparison yields equal, the next comparison is tried. You can of course chain as many comparisons as you can think of.