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

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

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

Вход = "дерево"

Ожидаемый результат: "eetr"

Поэтому мне нужна максимальная куча с использованием Priority Queue, но я не понял, как работает этот код. Как работает объявление Priority Queue?

    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());

вещь работает для создания приоритетной очереди.


java priority-queue max-heap
person AKASH SHIRALE    schedule 27.03.2020    source источник
comment
Отвечает ли это на ваш вопрос? Почему лямбда-выражение можно использовать в качестве компаратора?< /а>   -  person Progman    schedule 28.03.2020
comment
Спасибо за вашу помощь..   -  person AKASH SHIRALE    schedule 29.03.2020

Ответы (1)


arrow_upward
0
arrow_downward

Вы получили свой ответ в комментарии, который объясняет, что происходит в этом вызове конструктора. Я хочу объяснить, почему выражение 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 вместо сравнения — это старый трюк оптимизации, который люди используют и сегодня, не задумываясь о последствиях этого. И хотя это быстрее, чем вызов compareTo, в большинстве приложений разница не имеет значения. И это подвергает ваш код риску, о котором я упоминал выше. Это не очень хорошая практика.

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

person Jim Mischel    schedule 31.03.2020