Priority queue (Min Heap) ordering in Java

Question

I was working with the priority queue and came across this statement.

PriorityQueue<Integer> heap = new PriorityQueue<Integer>((n1, n2) -> n1 - n2);

Functionally I know this is a min-heap, but can someone explain to me how (n1, n2) -> n1 - n2 returns the smallest element?

Answer 1

The constructor accepts a Comparator<? super E> comparator.

Basically the statement (n1, n2) -> n1 - n2 is just a shorthand for

Comparator<Integer> result = new Comparator<Integer>() {
        @Override
        public int compare(Integer n1, Integer n2){
            return n1.compareTo(n2);
        }
    };

PriorityQueue<Integer> heap = new PriorityQueue<Integer>(result);

Answer 2

The question is already answered. I am just trying to add a simpler demonstration.

While using Comparator#compare, two integers are compared as following by the result of compare function.

 * Result is negative -> first element is smaller
 * Result is 0        -> they are same
 * Result is positive -> first element is greater

When you use n1 - n2:

* Result is negative -> n1 is smaller
* Result is 0        -> n1 and n2 are same
* Result is positive -> n1 is greater

When you use n2 - n1:

* Result is negative -> n2 is smaller
* Result is 0        -> n1 and n2 are same
* Result is positive -> n2 is greater

Edit

Following table is just to demonstrate that subtraction can be used for compare operations. If the operands and result does not fit into the datatype any operation will produce wrong result.

Answer 3

That's a comparator that will be used by this PriorityQueue instance to compare the items. It should be the implementation of the Comparator interface but here it reduced to the so-called lambda expression (n1, n2) -> n1 - n2.

By the way, in your case it's better to use the predefined comparators like Comparator.reverseOrder().

Answer 4

From the documentation for this PriorityQueue constructor:

Creates a PriorityQueue with the default initial capacity and whose elements are ordered according to the specified comparator.

So you're passing a lambda which provides the Comparator. Looking at its documentation:

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

So in our case, if n1 is smaller than n2, we will return a negative number, meaning that n1 is less than n2 and moving n1 closer to the top of the heap.

If we wanted to reverse the sort order, we could just change the lambda to:

(n1, n2) -> n2 - n1