Очередь приоритетов в Java (объявление Max Heap)

Question

Я бы sh сделал максимальную кучу в Java, но не смог этого понять. Может ли кто-нибудь объяснить мне это

Вопрос : По заданной строке отсортируйте ее в порядке убывания на основе частоты символов.

Input = "tree"

Ожидаемый вывод: "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()); 

работает для создания Приоритетной очереди.

Answer 1

Вы получили свой ответ в комментарии, который объясняет, что происходит в этом вызове конструктора. Я хочу объяснить, почему выражение 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())

В вашем конкретном случае это не проблема, потому что ваш счет не будет go отрицательным. На самом деле, в большинстве случаев, которые я видел, это не будет проблемой, потому что в большинстве случаев нет отрицательных чисел или просто недостаточно (или мало). Но дело не в этом.

Суть в том, что использование a - b вместо сравнения - это старый прием оптимизации, который люди до сих пор применяют сегодня, даже не задумываясь о последствиях этого. И хотя это быстрее, чем вызов compareTo, в большинстве приложений разница не имеет значения. И это подвергает ваш код риску, о котором я упоминал выше. Это не очень хорошая практика.

Как я уже говорил в прошлом: «Делать что-то, чтобы сэкономить несколько наносекунд, просто глупо».