java - 了解 PriorityQueue 比较器

Question

学习一些 DP 并遇到将 PQ 用作某些问题的堆，但是在我的头脑中很难清楚地了解比较器镜头手 lamda；

例如:

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 减去另一个 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 docs for priority queue ;

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).
The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.

当您想要存储没有自然排序的元素时，您可以让它们实现 Comparable接口(interface)或通过 Comparator到构造函数。递增/递减顺序取决于 Comparator. 的行为该方法通过返回一个整数来表示比较的结果。 Object A的比较至Object B必须返回0如果两个对象相等，则为 > 0 的整数如果Object A > Object B和一个整数 < 0如果Object A < Object B .

如果遵循此例程，优先级队列将按升序存储项目，即最小的项目将位于头部。如果您想将最大的项目存储在队列的头部，您的比较器应该相反地工作，例如，而不是返回 > 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反转优先级队列的顺序。