How do I make an array of Priority Queues? Further how to assign comparator function to each PQ in array

Question

I somehow came across a requirement to create an Array of PriorityQueues. A workaround could be to create a HashMap, but I prefered array.

I declared an Array of Priority Queues as follows.

PriorityQueue<long[]>[] arr = new PriorityQueue[10];

I wanted each Priority Queue in arr to have a same comparator function that sorts elements in PriorityQueue<long[]>, in order of second element inside long[].

I tried to fill the array arr using.

Arrays.fill(arr, new PriorityQueue<>(new Comparator<>(){
            public int compare(int[] a, int[] b){
                return b[1] - a[1];
            }
        }));

But this gives me an error, can anyone help what is wrong with this approach?

The Code:

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        PriorityQueue<long[]>[] arr = new PriorityQueue[10];
        Arrays.fill(arr, new PriorityQueue<>(new Comparator<>(){
            public int compare(int[] a, int[] b){
                return b[1] - a[1];
            }
        }));
    }
}

The Error:

Main.java:12: error: <anonymous Main$1> is not abstract and does not override abstract method compare(Object,Object) in Comparator
        Arrays.fill(arr, new PriorityQueue<>(new Comparator<>(){
                                                               ^
Main.java:13: error: method does not override or implement a method from a supertype
            public int compare(int[] a, int[] b){
                       ^
  (due to <>, every non-private method declared in this anonymous class must override or implement a method from a supertype)

Also is there a better way to assign object to each element of array during declaration?

Answer 1

To create an object with a comparator, you can use this approach:

PriorityQueue<Long[]> pq = new PriorityQueue<>(new Comparator<Long[]>() {
    public int compare(Long[] a, Long[] b) {
        return a[1].compareTo(b[1]);
    }
});

But note I have used Long not long and this allows me to also use compareTo instead of subtraction - to ensure you do not encounter unexpected out-of-bounds results for Compare's int return value.

---

The above uses the anonymous inner class approach you were looking to use in your question, but note also the explicit type Comparator<Long[]>.

As an optional extra step, this can be simplified by replacing the inner class with a lambda expression:

PriorityQueue<Long[]> pq = new PriorityQueue<>((Long[] a, Long[] b) -> a[1].compareTo(b[1]));

Therefore you can use either of the above approaches in your Arrays.fill.

Here is the lambda approach:

PriorityQueue<long[]>[] arr = new PriorityQueue[10];
Arrays.fill(arr, new PriorityQueue<>((Long[] a, Long[] b) -> a[1].compareTo(b[1])));

---

Just to note - that comparator may only be an artificial example for this question, but it is a bit unusual. And I was wondering if you actually meant to compare a[0] with b[0] instead.

And, obviously, all the queues are empty at this point.

---

Update

I completely agree with the comment from @OldDogProgrammer. Mixing generics and arrays in this way is not recommended. "Prefer lists to arrays" - Josh Bloch, Effective Java.

---

Update 2

You asked if I could:

provide some reference or some reading material

That is why I mentioned Josh Bloch and Effective Java. You can do an online search for "prefer lists to arrays josh bloch" to see various articles discussing this topic, in depth.

You asked:

what causes the error here?

You have not provided a specific type for new Comparator<>().

That is why I mentioned "note also the explicit type Comparator<Long[]>" in my answer (see above).

The objects you want the comparator to compare are Long[] arrays - but you provided int[] in your implementation:

compare(int[] a, int[] b)

You have not provided any type at all in your new Comparator<>() constructor - therefore it defaults to compare(Object,Object) - which you can see in the error message.

So, there is also a mismatch between the constructor and the implementation you have provided - as well as a mismatch between the constructor and what you should have provided in the implementation.

This is actually another Josh Bloch topic:

Prefer generic types.

There are excellent online articles about this topic, also. I expect there are also some excellent Stack Overflow answers about this, and "Prefer lists to arrays".

You can also search for terms covariant and invariant in the context of Java generics and arrays as another research topic.