How to build Priority Queue with customized comparator in linear time

Question

In the constructor of PriorityQueue, we can pass in a collection like List or Set, which builds the PriorityQueue in linear time. However, this also means the PriorityQueue will use a default Comparator.

I want to use my own comparator, so I can have something else other than a min heap. The only way I can think of is to wrap the collection in a SortedSet and put a customized comparator in it.

Is there any other good way to do this?

Basilio

Make a subclass of PriorityQueue w/ your Comparator overriding the default one? – Habakkuk

@ScottHunter all of the fields and methods in PriorityQueue class are not protect, so subclass can't override them. – Basilio

No, there isn't; this feature was omitted from PriorityQueue. There's no way to do what you want. – Rosemarierosemary

Answer 1

Assume you have class A (or a pojo) with an int priority; field which holds your priority for this object and its getter getPriority() then you have it something like this:

 Queue<A> queue = new PriorityQueue<>(
                    4 //initialCapacity
                 , new Comparator<A>() {
                public int compare(A p1, A p2) {
                    return Integer.valueOf(p1.getPriority()).compareTo(p2.getPriority());
                }
            });

Denim

my question is how build to a heap in LINEAR TIME with a comparator. your answer can't really do O(n), it will be O(nlog(n)). – Basilio

@Basilio then may be use correct a collection to insert items in the order you need with an appropriate speed? like ListIterator and create a queue out of it? see a sample here #18145320 – Denim

@Basilio also check the TreeSet for the queue if needed. see - #3608093 – Denim

Answer 2

Create proxy class that contains your data object and implements Comparable interface. Create list of such objects, pass it to PriorityQueue constructor.

I don't know of effective SortedSet implementations with garanteed creation time of O(n) for comparable objects. It is possible to sort array in O(n) for radix-friendly key though (in reality linear sort tends to be not-so-fast in general case), so you can make customized SortedSet with fast creation compatible to your special comparators.

Heap constructor for comparable objects can do it in O(n) only because it does not fully sort the list.

Cotyledon

There're no sorted collections with guaranteed O(n). TreeSet is good enough for log(n). HashSet is O(1) and being the best in the collections case and ISN'T sorted in any way either. :) – Denim

Well, not in standard library. But consider for a moment comparator that only takes into account priority level with only 4 gradations. Can you make such collection with constructor time O(n) and toArray time O(n)? – Cotyledon

Answer 3

In the constructor of PriorityQueue, we can pass in a collection like List or Set, which builds the PriorityQueue in linear time.

Wrong.

However, this also means the PriorityQueue will use a default Comparator.

Wrong.

---

The javadoc says

If the specified collection is an instance of a SortedSet or is another PriorityQueue, this priority queue will be ordered according to the same ordering.

So when starting from a recognized sorted collection, you get its Comparator. Moreover, you get linear time.

Otherwise, you don't. The source shows it rather clearly (look for heapify()).

If you have an unsorted list, there's no way to obtain a priority queue in linear time (unless the priority queue is ensuring the heap property lazily; but that's cheating).

Uncircumcision

quora.com/… This is an answer from quora. I should have mentioned I am ignoring sortedset and priorityqueue here. – Basilio

@Basilio In general I wouldn't trust quora much, but this answer is really good. However, I'm unsure what you really want to know. AFAIK the Java PriorityQueue is optimal w.r.t. the construction. If you feed it with a properly ordered input, it can take advantage of it. Otherwise, it must make its heap (which is sort of half of sorting). +++ You may want to edit you question, so it gets clear. – Uncircumcision

Answer 4

I have the same problem.

The only thing that I think is create a wrapper class that contains an object T and implements Comparable interface like this:

class ModifiedPriorityQueue<T> extends PriorityQueue<Wrapper<T>> {

    public ModifiedPriorityQueue(Collection<T> collection, Comparator<T> comparator) {
        super(collection.stream().map(x -> new Wrapper<>(x, comparator)).collect(Collectors.toList()));
    }
}

class Wrapper<T> implements Comparable<Wrapper<T>> {

    private final T object;
    private Comparator<T> comparator;

    public Wrapper(T object, Comparator<T> comparator) {
        this.object = object;
        this.comparator = comparator;
    }

    @Override
    public int compareTo(Wrapper<T> o) {
        return comparator.compare(object, o.object);
    }

    @Override
    public String toString() {
        return object.toString();
    }
}

class Main {
    public static void main(String[] args) {
        Collection<Integer> elements = Arrays.asList(1, 2, 3, 4);
        ModifiedPriorityQueue<Integer> p = new ModifiedPriorityQueue<>(elements, Comparator.reverseOrder());

        while (!p.isEmpty()) {
            System.out.println(p.poll());
        }
    }
}

Mathi