Понимание компараторов PriorityQueue

Question

Изучение некоторого DP и обнаружение PQ использовалось как куча для определенных проблем, однако, зная, что лямда выстрела руки компаратора становится трудно найти в моей голове,

Например:

class Interval {
  int start = 0;
  int end = 0;

  Interval(int start, int end) {
    this.start = start;
    this.end = end;
  }
}

PriorityQueue<Integer> maxStartHeap = new PriorityQueue<>(n, (i1, i2) -> intervals[i2].start - intervals[i1].start);
PriorityQueue<Integer> maxEndHeap = new PriorityQueue<>(n, (i1, i2) -> intervals[i2].end - intervals[i1].end);

как один int минус другой создает желаемый наименьший или наибольший первый порядок? Я хочу поиграть с возможными реализациями, но не знаю с чего начать. Может ли кто-то указать мне на ресурс, который мог бы объяснить, что именно происходит, например, внешний вид компаратора, если он выглядит на основе наибольшего отрицательного числа, является высшим приоритетом, но это только предположение.

полный код для полноты :

import java.util.*;

class Interval {
  int start = 0;
  int end = 0;

  Interval(int start, int end) {
    this.start = start;
    this.end = end;
  }
}

class NextInterval {
  public static int[] findNextInterval(Interval[] intervals) {
    int n = intervals.length;
    // heap for finding the maximum start
    PriorityQueue<Integer> maxStartHeap = new PriorityQueue<>(n, (i1, i2) -> intervals[i2].start - intervals[i1].start);
    // heap for finding the minimum end
    PriorityQueue<Integer> maxEndHeap = new PriorityQueue<>(n, (i1, i2) -> intervals[i2].end - intervals[i1].end);
    int[] result = new int[n];
    for (int i = 0; i < intervals.length; i++) {
      maxStartHeap.offer(i);
      maxEndHeap.offer(i);
    }

    // go through all the intervals to find each interval's next interval
    for (int i = 0; i < n; i++) {
      int topEnd = maxEndHeap.poll(); // let's find the next interval of the interval which has the highest 'end' 
      result[topEnd] = -1; // defaults to -1
      if (intervals[maxStartHeap.peek()].start >= intervals[topEnd].end) {
        int topStart = maxStartHeap.poll();
        // find the the interval that has the closest 'start'
        while (!maxStartHeap.isEmpty() && intervals[maxStartHeap.peek()].start >= intervals[topEnd].end) {
          topStart = maxStartHeap.poll();
        }
        result[topEnd] = topStart;
        maxStartHeap.add(topStart); // put the interval back as it could be the next interval of other intervals
      }
    }
    return result;
  }

  public static void main(String[] args) {
    Interval[] intervals = new Interval[] { new Interval(2, 3), new Interval(3, 4), new Interval(5, 6) };
    int[] result = NextInterval.findNextInterval(intervals);
    System.out.print("Next interval indices are: ");
    for (int index : result)
      System.out.print(index + " ");
    System.out.println();

    intervals = new Interval[] { new Interval(3, 4), new Interval(1, 5), new Interval(4, 6) };
    result = NextInterval.findNextInterval(intervals);
    System.out.print("Next interval indices are: ");
    for (int index : result)
      System.out.print(index + " ");
  }
}

Answer 1

Из документов Java для приоритетной очереди ;

Неограниченная приоритетная очередь, основанная на куче приоритетов. Элементы очереди с приоритетами упорядочиваются в соответствии с их естественным порядком или компаратором, предоставляемым во время построения очереди, в зависимости от того, какой конструктор используется. Очередь приоритетов не разрешает нулевые элементы. Очередь приоритетов, основанная на естественном упорядочении, также не позволяет вставлять несопоставимые объекты (это может привести к ClassCastException).
Заголовок этой очереди является наименьшим элементом по отношению к указанному упорядочению. Если несколько элементов связаны для наименьшего значения, один из этих элементов является заголовком - связи нарушаются произвольно. Операции извлечения очереди опрашивают, удаляют, просматривают и элемент обращаются к элементу в начале очереди.

Если вы хотите хранить элементы, которые не имеют естественного упорядочения, вы можете либо заставить их реализовать интерфейс Comparable, либо передать Comparator в конструктор. Порядок увеличения / уменьшения зависит от поведения Comparator.. Этот метод указывает результат сравнения, возвращая целое число. Сравнение Object A с Object B должно вернуть 0, если два объекта равны, целое число, равное > 0, если Object A > Object B, и целое число, равное < 0, если Object A < Object B.

* 1021. * Если вы следуете этой процедуре, приоритетная очередь будет хранить элементы в возрастающем порядке, то есть наименьший элемент будет находиться во главе. Если вы хотите сохранить самый большой элемент в начале очереди, ваш компаратор должен работать обратно, например, вместо того, чтобы возвращать целое число, равное > 0, когда Object A > Object B, вернуть целое число, равное < 0, и вернуть целое число, которое > 0, когда Object A < Object B.

Если ваша очередь хранит целые числа, int a - int b вернет > 0, когда a > b, вернет 0, когда a == b, и вернет < 0, когда a < b, вот почему это работает. Вы можете вернуть int b - int a, чтобы изменить порядок очередности.

Answer 2

Это аналогично этому:

new PriorityQueue<>(n, new Comparator<Integer>() {
    public int compare(Integer one, Integer two) {
        return intervals[one] - intervals[two];
    }
});

Тем не менее, вы, вероятно, не хотите, чтобы сортировка компаратора основывалась на внешнем массиве. Я бы опубликовал больше вашего кода (например, как вы используете intervals). Comparator в этом случае - для упорядочивания элементов в пределах PriorityQueue; вы, вероятно, хотите сравнить их интервалы в очереди из Interval объектов:

class Interval {

    //...

    public int difference() {
        return this.end - this.start;
    }        
}

PriorityQueue<Interval> values = new PriorityQueue((i1, i2) -> Integer.compare(i1.difference(), i2.difference()));
//AKA
PriorityQueue<Interval> values = new PriorityQueue(Comparator.comparingInt(Interval::difference)));

Это будет сортировать values на основе соответствующих значений Interval#difference. Я бы больше посмотрел на функции api и ссылки на методы, если вы все еще немного отстаете от Java 8. Также смотрите: Документация компаратора .