在对象和值之间创建映射的最小堆

Question

这些问题是用Java提出的。

我有一个对象，我们把它叫做MyObj。另外，我有一种方法可以为这个对象的每个实例打分。但是，评分也取决于另一个整数值。所以，我使用表

在填充这些值时，我希望每次都从当前已知的最小值开始。当我说最小值时，我的意思是在所有可能的MyObj x实例和所有可能的整数I上，我看到的是值的最小值。获取（x，i），它存在于的值中（因此，首先，它将是我输入的初始值，然后，取决于计算的值）。

因此，最简单的方法是实现最小堆。为此，我创建了：PriorityQueue

这在第一次迭代中效果很好。问题是，我只知道最小值，而不知道导致该最小值的x和I。也就是说，我想让最小堆知道，当我按double的值排序时，我还想保留一个指向这些x和I的指针，它们将我带到这个值。

我读了一些关于实现比较器的内容。这意味着，我想创建某种类型的对象，比如说MyObj和int的组合，然后为它们实现一个比较器？但是这个比较器将取决于表value esOf中的值。

我不确定这样做是否正确。如果是的话，我有点困惑，不知道该怎么做。但也许有更好的方法？




Answer 1

如果要在集合（如PriorityQueue中保留键和值，则需要使用包含所有这些值的引用的对象。而您可以尝试使用像Tuple这样的泛型类

class HeapEntry {
  private MyObj x;
  private int i;
  private double value;

  //constructor, getters and setters omitted
}

然后使用比较器

PriorityQueue<HeapEntry> minHeap = new PriorityQueue(Comparator.comparing(HeapEntry::getValue);

Comparator.comparing（HeapEntry::getValue）正在使用方法引用，也可以重写为Comparator.comparing

//creating an anonymous implementation of Comparator
Comparator<HeapEntry> heapComp = new Comparator<HeapEntry>() {
  public int compare(HeapEntry left, HeapEntry right) {
    //easy to do with primitives
    //if you're using wrapper objects you need to deal with nulls, i.e. decide whether a null value is greater or lower than a non-null value
    return Double.compare(left.getValue(), right.getValue());
  }
};