Может кто-нибудь объяснить мне PriorityQueue в этом примере? - PullRequest
0 голосов
/ 26 сентября 2018

Я пытаюсь научиться использовать PriorityQueue, поскольку я никогда не использовал его раньше.Вот пример использования, которое я нашел на LeetCode для задачи, которая находит элементы Top K в массиве строк

public List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> count = new HashMap();
    for (String word: words) {
        count.put(word, count.getOrDefault(word, 0) + 1);
    }
    PriorityQueue<String> heap = new PriorityQueue<String>(
            (w1, w2) -> count.get(w1).equals(count.get(w2)) ?
            w2.compareTo(w1) : count.get(w1) - count.get(w2) );

    for (String word: count.keySet()) {
        heap.offer(word);
        if (heap.size() > k) heap.poll();
    }

    List<String> ans = new ArrayList();
    while (!heap.isEmpty()) ans.add(heap.poll());
    Collections.reverse(ans);
    return ans;
}

Более примечательно, что я хотел бы знать, что делает эта строка:

PriorityQueue<String> heap = new PriorityQueue<String>(
            (w1, w2) -> count.get(w1).equals(count.get(w2)) ?
            w2.compareTo(w1) : count.get(w1) - count.get(w2) );

Может ли кто-нибудь объяснить с точки зрения хромого человека, что здесь происходит?Есть ли способ переписать компаратор как обычный оператор if?

Спасибо за любую помощь.

Ответы [ 2 ]

0 голосов
/ 26 сентября 2018

Выражение, которое вы используете в конструкторе, является лямбда-выражением .Поскольку Comparator - это функциональный интерфейс, то есть интерфейс только с одним абстрактным методом, лямбда-выражение может использоваться как сокращение для создания анонимного класса.

В вашем примере,

new PriorityQueue<String>((w1, w2) -> count.get(w1).equals(count.get(w2)) ? w2.compareTo(w1) : count.get(w1) - count.get(w2));

функционально эквивалентно

new PriorityQueue<String>(new Comparator<String>() {
    public int compare(String w1, String w2) {
        return count.get(w1).equals(count.get(w2)) ? w2.compareTo(w1) : count.get(w1) - count.get(w2);
    }
});

Это также было бы то же самое, что создать отдельный класс, реализующий Comparator<String>, и передать экземпляр этого класса в качестве параметра.на PriorityQueue.

Что касается записи Comparator в качестве оператора if, короткий ответ - нет.Компаратор должен быть экземпляром Comparator<String>.Однако, возможно, более понятная версия того же компаратора выглядит следующим образом:

new PriorityQueue<String>((w1, w2) -> {
    if (count.get(w1).equals(count.get(w2))) { // If the counts of w1 and w2 are the same,
        return w2.compareTo(w1); // Then return the reverse lexicographical ordering of w1 and w2 (e.g. "Zebra" comes before "Apple")
    } else if (count.get(w1) < count.get(w2)) {
        return -1; // w1 comes before w2
    } else {
        return 1; // w1 comes after w2
    }
});

Примечание: «Лексикографическое упорядочение» - это, в основном, алфавитное упорядочение, но основанное на кодах ASCII.Для получения дополнительной информации см. String#compareTo(String)

Надеюсь, это поможет!

0 голосов
/ 26 сентября 2018

Используемый вами конструктор PriorityQueue объявляется как:

public PriorityQueue(Comparator<? super E> comparator)

Требуется компаратор объекта аргумента универсального типа.Параметр конструктора comparator описывается следующим образом:

компаратор, который будет использоваться для упорядочения этой очереди приоритетов.Если ноль, будет использоваться естественный порядок элементов.

В вашем вызове аргументом является лямбда-выражение , которое обеспечивает реализации Comparator<String>.Это примерно эквивалентно следующему анонимному классу:

PriorityQueue<String> heap2 = new PriorityQueue<String>(new Comparator<String>() {
    @Override
    public int compare(String w1, String w2) {

        if(count.get(w1).equals(count.get(w2))) {
            return w2.compareTo(w1);
        } else {
            return count.get(w1) - count.get(w2);
        }

        // can also just be (without the if/else above):
        //return count.get(w1).equals(count.get(w2)) ? w2.compareTo(w1) : count.get(w1) - count.get(w2);
    }
});
...