了解优先级队列比较器

Question

学习一些DP并遇到PQ用作某些问题的堆，但是知道比较器射击手lamdas在我的脑海中变得很难找到清晰;

例如：

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，如果Object A > Object B则返回一个> 0的整数，如果Object A < Object B则返回一个< 0的整数。

如果您遵循此例程，优先级队列将按递增顺序存储项目，即最小的项目将位于头部。如果要将最大的项目存储在队列的头部，则比较器应该反向工作，例如，与其返回Object A > Object B时> 0的整数，不如返回< 0的整数，并返回Object A < Object B时> 0的整数。

如果您的队列存储整数，int a - int b将在a > b时返回> 0，在a == b时返回0，在a < b时返回< 0，这就是它工作的原因。您可以返回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)));

这将根据Interval#difference的相应值对values进行排序。如果你在 Java 8 上仍然有点落后，我会更多地研究函数 api 和方法引用。另请参阅：比较器文档。