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 Integerpare(b.getValue(), a.getValue());
            }
            return a.getKey()pareTo(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;
}

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 Integerpare(b.getValue(), a.getValue());
            }
            return a.getKey()pareTo(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;
}

• java
• hashmap
• priority-queue

• 4 You are comparing Integers, not primitive ints. != should not be used as it is not doing a comparison of values, but checking reference equality – pebble unit Commented Feb 18 at 1:09
• Why did you move b to the left in your comparison of values? This return Integerpare(b.getValue(), a.getValue()); looks quite wrong. – Elliott Frisch Commented Feb 18 at 1:28
• How is accountA(200), accountB(200), accountC(200) considered descending order? Please provide different examples showing how you want the values to poll. – WJS Commented Feb 18 at 2:25
• 1 When I replaced your incorrect != with .equals(), I got the accounts in alphabetical order, A, B, C. – Anonymous Commented Feb 18 at 2:40
• 1 @ElliottFrisch the b is on the left of a because the comparison needs to be reversed. The method name topSpenders makes that obvious; otherwise it would be called lowestSpenders. – k314159 Commented 2 days ago

1 Answer 1

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 Integerpare(b.getValue(), a.getValue());
    }
    return a.getKey()pareTo(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_COMPARATORpare(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 Integerpare(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.