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

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().

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

Related

Recent Posts