0

我希望在 Java 中创建一个最大堆，但无法理解这一点。谁可以给我解释一下这个

问题：给定一个字符串，根据字符的频率按降序对其进行排序。

输入=“树”

预期输出：“eetr”

所以我需要一个使用优先队列的最大堆，但我不明白这段代码是如何工作的。优先队列的声明是如何工作的？

    public class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);

        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        pq.addAll(map.entrySet());

        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            Map.Entry e = pq.poll();
            for (int i = 0; i < (int)e.getValue(); i++) 
                sb.append(e.getKey());
        }
        return sb.toString();
    }
}

所以想知道这是怎么回事

new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());

事情适用于制作优先队列。

4

1 回答 1

0

您在评论中得到了答案，该评论解释了该构造函数调用中发生的情况。我想解释一下为什么b.getValue() - a.getValue()不应该将表达式用作比较函数。

回顾一下，表达式似乎起作用的原因是因为比较器的语义是这样的，当它用 (a,b) 调用时，然后：

. 如果结果 < 0，则 a < b 。如果结果为 0，则 a == b 。如果结果 > 0，则 a > b

因此，给定两个整数，则compare(a, b)变为result = a - b，显然这是可行的。或者至少它适用于大多数人会测试的简单案例。

但大多数人不测试整数溢出。设想

a = INTEGER.MAX_VALUE;
b = -1;

现在你有问题了。表达式a - b导致整数溢出，结果为INTEGER.MIN_VALUE. 所以它错误地报告INTEGER.MAX_VALUE小于-1。

任何a足够正且b足够负以导致整数溢出的时间，使用减法代替比较都会给您错误的结果。

比较的正确方法是使用比较方法。例如：

a.getValue().compareTo(b.getValue())

在您的特定情况下，这不是问题，因为您的计数不会变为负数。事实上，在我见过的大多数情况下，这不会成为问题，因为大多数用法没有负数，或者数字不够大（或小）。但这不是真正的重点。

真正的要点是，使用a - b代替比较是一种古老的优化技巧，人们今天仍在使用它，而没有考虑这样做的后果。而且，虽然它比 call 更快，但compareTo在大多数应用程序中，区别并不重要。它使您的代码面临我上面提到的风险。这不是一个好习惯。

正如我过去所说，“做一些事情来节省几纳秒只是愚蠢的。”

于 2020-03-31T17:50:23.740 回答