Is There a Priorityqueue Implementation with Fixed Capacity and Custom Comparator

Is there a PriorityQueue implementation with fixed capacity and custom comparator?

You could use a SortedSet e.g. TreeSet with a custom comparator and remove the smallest when the size reachs N.

How to create a priority queue with an initial capacity and custom comparator in lambda notation?

The problem is that int and Integer are not—exactly—the same thing. One is a primitive data type, the other is an Object wrapper around that primitive data type, and while Java 5 introduced Autoboxing/Autounboxing to make code that interchanges between the two less painful to write, it's still incorrect to treat them like they're the same. In this case, the lambda expression is trying to match the definition of a Comparator<int> (which cannot exist), and the queue is expecting a Comparator<Integer>, which is valid and legal.

The simplest solution is to just let the lambda expression deduce the argument types:

PriorityQueue<Integer> queue = new PriorityQueue<>(8, (v, w) -> Double.compare(prior[v], prior[w]));

This should compile perfectly fine and do what you expect of it.

How to set fixed size to PriorityQueue in Java?

As the oracle documentation here states,
http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html:

A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically. The details of the growth policy are not specified.

A possible workaround may be that you can check the size before performing any operation:

if (q.size() <= QUEUE_LIMIT)
     //your code

How to create a PriorityQueue with new comparator and NO specified initial capacity?

Modern answer, as of 2021: https://stackoverflow.com/a/30015986/139010

---

Pre-Java-8 answer, for posterity:

There is no such constructor. As per the JavaDocs, the default capacity is 11, so you could specify that for analogous behavior to the no-arg PriorityQueue constructor:

Queue<Node> theQueue = new PriorityQueue<Node>(11,new Comparator<Node>());

And yes, the queue will grow if it needs to.

A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically. The details of the growth policy are not specified.x

Trying to understand PriorityQueue

Regarding constructors

PriorityQueue already have a zero argument constructor. You can see this yourself
easily if you read the javadocs. Whether or not this suits your purpose I can't say. It
does require that you use a type that implements comparable (e.g. String, Integer)
otherwise the queue will have no way of knowing how to order the elements.

capacity in the case of PriorityQueue is not a max capacity, but just a hint about
how many elements you think will be in the queue at the same time. It has only performance
implications, the semantics of they queue are completely independent of this.

Storage and retrieval semantics

The values are stored (inserted) in any order but are retrieved in order. That is the
point of a priority queue. A list that is automatically sorted every time you append to
it will give you exactly the same semantics as javas PriorityQueue. The list implementation would be very inefficient thought, so that's why you use a heap instead.

I'm not sure if this is a response to what you are asking, so if it's not please
clarify what you are confused about.

How do I use a PriorityQueue?

Use the constructor overload which takes a Comparator<? super E> comparator and pass in a comparator which compares in the appropriate way for your sort order. If you give an example of how you want to sort, we can provide some sample code to implement the comparator if you're not sure. (It's pretty straightforward though.)

As has been said elsewhere: offer and add are just different interface method implementations. In the JDK source I've got, add calls offer. Although add and offer have potentially different behaviour in general due to the ability for offer to indicate that the value can't be added due to size limitations, this difference is irrelevant in PriorityQueue which is unbounded.

Here's an example of a priority queue sorting by string length:

// Test.java
import java.util.Comparator;
import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        Comparator<String> comparator = new StringLengthComparator();
        PriorityQueue<String> queue = new PriorityQueue<String>(10, comparator);
        queue.add("short");
        queue.add("very long indeed");
        queue.add("medium");
        while (queue.size() != 0) {
            System.out.println(queue.remove());
        }
    }
}

// StringLengthComparator.java
import java.util.Comparator;

public class StringLengthComparator implements Comparator<String> {
    @Override
    public int compare(String x, String y) {
        // Assume neither string is null. Real code should
        // probably be more robust
        // You could also just return x.length() - y.length(),
        // which would be more efficient.
        if (x.length() < y.length()) {
            return -1;
        }
        if (x.length() > y.length()) {
            return 1;
        }
        return 0;
    }
}

Here is the output:

short

medium

very long indeed

why does priority queue constructor take capacity with comparator?

I don't think there's a hard-and-fast reason for this. There's no fundamental reason why you can't do this - it would be trivial to add by just doing this:

public PriorityQueue(`Comparator<? super E> comparator) {
    this(/* reasonable default */, comparator);
}

My guess is that it was an oversight in the design. As @Sotirios Delimanolis pointed out in the comment, in Java 8 this constructor will be added.

Hope this helps!

Why does the Java PriorityQueue implementation use Comparator? super E and not simply ComparatorE

Because why not.

Given a comparator that can compare any 2 CharSequence objects (CharSequence is an interface; String, StringBuilder, and a few other things implement it), then.. that is just as good when you have a need to compare only strings. All Strings are also CharSequences, so a comparator that can tell you for any 2 charsequence objects which one 'comes first' can do the job perfectly well.

Generics are invariant by default, so if you have a PriorityQueue<String>, and it worked like you want to, it'd look like Comparator<E>, which means Comparator<String>, and a Comparator<CharSequence> is not compatible with that. Like passing a String to a method that wants an Integer object, it just doesn't compile.

Hence, <? super E> so that you can pass a Comparator<CharSequence>.

It doesn't come up often, of course, but it's 'more correct' this way. I'm sure you'd be surprised if you so happen to have a comparator of CharSequences laying about and can't use it to power a PriorityQueue<String>.

---

Related Topics