Порядок приоритетной очереди (Min Heap) в Java

Question

Я работал с очередью приоритетов и наткнулся на это утверждение.

PriorityQueue<Integer> heap = new PriorityQueue<Integer>((n1, n2) -> n1 - n2);

Функционально я знаю, что это минимальная куча, но может кто-нибудь объяснить мне, как (n1, n2) -> n1 - n2 возвращает наименьший элемент?

Answer 1

Конструктор принимает Comparator<? super E> comparator.

По существу, выражение (n1, n2) -> n1 - n2 является просто сокращением для

Comparator<Integer> result = new Comparator<Integer>() {
        @Override
        public int compare(Integer n1, Integer n2){
            return n1.compareTo(n2);
        }
    };

PriorityQueue<Integer> heap = new PriorityQueue<Integer>(result);

Answer 2

Из документации для этого PriorityQueue конструктора :

Создает PriorityQueue с начальной емкостью по умолчанию и элементы которой упорядочены в соответствии с указанным компаратором.

Итак, вы передаете лямбду, которая обеспечивает Comparator. Глядя на его документацию :

Сравнивает два аргумента для порядка. Возвращает отрицательное целое число, ноль или положительное целое число, поскольку первый аргумент меньше, равен или больше второго.

Так что в нашем случае, если n1 меньше n2, мы будем возвращать отрицательное число, означающее, что n1 меньше n2 и перемещается n1 ближе к вершине кучи.

Если мы хотим изменить порядок сортировки, мыможно просто изменить лямбду на:

(n1, n2) -> n2 - n1

Answer 3

Это компаратор, который будет использоваться этим экземпляром PriorityQueue для сравнения элементов. Это должна быть реализация интерфейса Comparator, но здесь он сводится к так называемому лямбда-выражению (n1, n2) -> n1 - n2.

Кстати, в вашем случае лучше использовать предопределенные компараторы, такие как Comparator.reverseOrder().

Answer 4

На вопрос уже дан ответ. Я просто пытаюсь добавить более простую демонстрацию.

При использовании сравнения Comparator # два целых сравниваются следующим образом в результате функции сравнения.

 * Result is negative -> first element is smaller
 * Result is 0        -> they are same
 * Result is positive -> first element is greater

Когда вы используете n1 - n2:

* Result is negative -> n1 is smaller
* Result is 0        -> n1 and n2 are same
* Result is positive -> n1 is greater

Когда вы используете n2 - n1:

* Result is negative -> n2 is smaller
* Result is 0        -> n1 and n2 are same
* Result is positive -> n2 is greater

Редактировать

Следующая таблица просто демонстрирует, что вычитание можно использоватьдля сравнения операций. Если операнды и результат не вписываются в тип данных, любая операция приведет к неверному результату.