Creating a minimum heap of a mapping between an object and a value

Admin 1
Viewed 61

The questions is in Java.

I have some sort of an Object, lets call it MyObj. Additionally, I have a way to score each instance of this object. However, the scoring depends also on another integer value. So, I use Table<MyObj,Integer,Double> valuesOf to store the values. I'd like to emphasize that I begin with a single value inserted in valuesOf, and the rest is being filled on the fly.

While filling these values, I'd like to start each time with the currently best known minimal value. When I say minimal value, I mean that over all possible instances of MyObj x and all possible integers i, I'm looking at the smallest value of valuesOf.get(x,i) that exists in valuesOf (so at first, it will be this initial value I'm putting in, and later, well, depends on the values calculated).

So the easiest way is to implement a minimum heap. To do so, I created: PriorityQueue<Double> minHeap = new PriorityQueue<>(). Then, each time a new value currNewVal has been calculated, I added valuesOf.put(x,i,currNewVal) and minHeap.add(currNewVal). Each time I want to know the current lowest value, I perform: Double currValue = minHeap.remove().

This works fine for the first iteration. The problem is, I keep knowledge only of the minimal value, and not of the x and i that resulted in this minimal value. That is, I somehow want to keep the minimal heap aware that, while I am sorting by the value of the double, I am also interested in keeping a pointer to these x and i that brought me to this value.

I read a bit about implementing comparators. And that means, that I want to create some sort of an object, lets say a combination of MyObj and an int, and then to implement a comparator for them? But this comparator will be depending on the value from the table valuesOf.

I'm not sure this is the right way to go for it. And if it is, I got a bit confused and not sure how exactly to do so. But perhaps there are better ways?

minimum comparator heap object java
1 Answers

If you want to keep the keys as well as the value in a collection like a PriorityQueue need to use an object contains references to all of those values. While you could try to use generic classes like Tuple<MyObj, Integer, Double> in many cases it's best to create a more specific class that makes it easier to understand the individual components, e.g. something like this:

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

  //constructor, getters and setters omitted
}

Then use a Comparator<HeapEntry> to go along with a PriorityQueue<HeapEntry>:

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

Comparator.comparingDouble(HeapEntry::getValue) is using a method reference and could also be rewritten as Comparator.comparingDouble(entry -> entry.getValue()). Before lambdas were available the comparator could have looked like this:

//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());
  }
};

Note: before the edit the code was using Comparator.comparing(...) to build the comparator which is fine is the value uses the wrapper type Double. However, since the type of value is double, i.e. the primitive type, we need to use Comparator.comparingDouble().

user_6378530
Related