Understanding PriorityQueue comparators

Question

Learning some DP and coming across PQ used as heaps for certain problems, however knowing the comparator shot hand lamdas is becoming hard to find clear in my head;

For instance:

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);

how does one int minus another create the desired smallest or largest first ordering? I want to play around with possible implementations but don't know where to start. Can someone point me to a resource that could explain what exactly is happening, for the look of the comparator if it looks based on the largest -negative number is top priority but thats just a guess.

full code for completeness:

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

From the 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.

When you want to store elements that don't have natural ordering, you can either have them implement the Comparable interface or pass a Comparator to the constructor. The increasing/decreasing order depends on the behavior of the Comparator. This method indicates the result of comparison by returning an integer. A comparison of Object A to Object B must return 0 if two objects are equal, an integer that is > 0 if Object A > Object B and an integer that is < 0 if Object A < Object B.

If you follow this routine, the priority queue will store the items in increasing order, i.e. smallest item will be at the head. If you want to store the largest item at the head of the queue, your comparator should work inversely, e.g instead of returning an integer that is > 0 whenObject A > Object B, return an integer that is < 0 and return an integer that is > 0 when Object A < Object B.

If your queue stores integers, int a - int b will return > 0 when a > b, will return 0 when a == b and will return < 0 when a < b, that's why it works. You can return int b - int a to reverse the order of priority queue.

Answer 2

It's analogous to this:

new PriorityQueue<>(n, new Comparator<Integer>() {
    public int compare(Integer one, Integer two) {
        return intervals[one] - intervals[two];
    }
});

That said, you're probably not looking to have your comparator sort based around an external array. I would post more of your code (e.g. how you're using intervals). The Comparator in this case is for ordering elements within the PriorityQueue; you're probably looking to compare their intervals within a queue of Interval objects:

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)));

This will sort values based on the respective values of Interval#difference. I would look more into the function api and method references if you're still a bit behind on Java 8. Also see: Comparator documentation.