create PriorityQueue in O(n ) with custom comparator

Question

I was trying to implement MST with Priorityqueue with custom comparator, but I am facing problem in building min-heap with it in O(n) time. The problem is only one constructor of Priorityqueue allows to create PriorityQueue in O(n), but it does not take any comparator as argument. I want it to use my custom comparator. Is there workaround for this problem ? PriorityQueue.addAll() will lose the purpose of using Min-heap for MST as it is O(nlogn) method. Here is my code.

ArrayList <edge>ar=new ArrayList<>(); 
   for(int i=0;i<e;i++)
   {
       int u=ss.nextInt();
       int v=ss.nextInt();
       int w=ss.nextInt();
       ar.add(new edge(u,v,w));
   }
   PriorityQueue <edge>pr=new PriorityQueue<edge>(ar);

And the comparator that I want to use:-

PriorityQueue <edge>ar=new PriorityQueue(11,new Comparator() {
        @Override
        public int compare(Object o1, Object o2) {
            edge n1=(edge) o1;
            edge n2=(edge) o2;
            if(n1.w<n2.w)
            {
                return -1;
            }
            else if(n1.w==n2.w)
            {
                if((n1.u+n1.v+n1.w)<=(n2.u+n2.v+n2.w))
                {
                    return -1;
                }   
                else
                {
                    return 1;
                }
            }
            else
            {
                return 1;
            }
        }
    });

Desmonddesmoulins

show your work please – Lucas

@Lucas updated. – Desmonddesmoulins

PriorityQueue.addAll() ... is O(nlogn) method. Do you have any evidence for this? – Breathy

Actually I am confused with accepted answer of this post. #34693914 – Desmonddesmoulins

@Desmonddesmoulins I was incorrect that you cannot create it in O(n) time from scratch... been a while since I was in Data Structures!! :) – Exsanguine

@jrook: PriorityQueue inherits addAll from AbstractQueue. It does not override the implementation. Documentation for AbstractQueue.addAll says, This implementation iterates over the specified collection, and adds each element returned by the iterator to this queue, in turn. That'll be O(n log n). – Variegation

@Breathy I looked at the source and addAll uses for(E e : c) add(e) - no heapify involved - there's nothing to stop it from appending to the array and calling a single heapify though, which in all honesty I'm surprised it doesn't do, even if truth be told the difference between n and n lg n is pretty darned small. – Exsanguine

Answer 1

If you have not min-heap-ordered your list elsewhere, you will not be able to new PriorityQueue(...) anything and somehow avoid the hit of creating your heap. The math here says it's O(n) for the average case, but it is still more than just iterating.

PriorityQueue<edge> pr = new PriorityQueue<edge>(ar, comp) {
    PriorityQueue(List<edge> ar, Comparator<edge> c) {
        this(c);
        for(int i = 0; i < queue.length; i++) {
            queue[i] = ar.get(i);
        }
        this.size = queue.length;
        heapify(); // O(n), except that heapify is private and thus you can't call it!!!
    }
}

Now I haven't tested this, it's just off the top of my head with some guidance from the PriorityQueue source, but it should point you in the right direction.

But sometime you have to pay the piper and create the heap-order and that be more than just iteration. It should still be on O(n) though, because of heapify.

Another option is to have edge implement Comparable<edge>. Then you can just PriorityQueue<edge> pr = new PriorityQueue(ar);

If you cannot control edge implements Comparable<edge> then you could compose a container class:

class EdgeContainer implements Comparable<EdgeContainer> {

    private static final Comparator<edge> comp = ; // that comparator above
    private final edge edge;
    EdgeContainer(Edge edge) { this.edge = edge; }
    public int compareTo(EdgeContainer e) { return comp.compare(edge, e.edge); }
    public edge getEdge() { return edge; }
}

List <EdgeContainer>ar=new ArrayList<>(); 
for(int i=0;i<e;i++)
{
   int u=ss.nextInt();
   int v=ss.nextInt();
   int w=ss.nextInt();
   ar.add(new EdgeContainer(new edge(u,v,w)));
}

PriorityQueue<EdgeContainer> qr = new PriorityQueue(ar);

Exsanguine

Answer 2

Java's PriorityQueue takes O(n) time to create a priority queue out of a collection passed to it. The mathematical proof has been given in CLSR chapter 6.4 (page 157 in 3rd edition). Intuitively, as the underlying array is mutated into a heap using siftDown or siftUp, the size of the number of the elements to loop over for the next sift operation also decreases leading to an O(n) time complexity.

But as discussed in the comments and as you have mentioned in your question, you cannot achieve this time complexity by using addAll(). The reason is adAll() is inherited from AbstractQueue and works by adding elements in the collection one by one to the queue which can lead to O(nlogn) time complexity.

So if having O(n) time complexity is an absolute requirement, you will have no option but to implement the Comparator interface for the class of objects contained in the collection. @corsiKa's answer nicely details this approach. Also note that even if you pass a collection directly to PriorityQueue, it will convert it to an array which is basically another O(n) operation.

Breathy

In a way, he does, because he can't add a collection and a comparator in the same constructor... and using addAll sifts up, not down... – Exsanguine

@corsiKa, you are right. But won't that be fixed by implementing compareTo() for the object contained in the collection? – Breathy

Yes, that's a possibility - OP may or may not be able to control that - although he could compose a container class? – Exsanguine

@Breathy will that work for PriorityQueue for natural ordering ? – Desmonddesmoulins

@rainyday: in that case you will be stuck with the ordering PriorityQueue's default constructor gives you. If you don't like that ordering and if you can, you may implement comparing at the class level and pass the collection of that class to PriorityQueue. corsiKa's answer gives more detail about this. – Breathy

@rainyday, I wanted to emphasize the point that if you are happy with the queue the default constructor gives you, you don't need to worry about time complexity. – Breathy

Whereas the O(1) argument (see #39514969) is interesting from a theoretical point of view, actual running time tells a different story. Calling add a million times is slower than having the constructor create a heap from it. It's easy enough to provide a Comparable interface or, if you have no control over the class, a container that implements its own Comparable interface. – Variegation

@JimMischel, the argument that building heap takes O(n) time does not rely upon average insertion time of O(1). If we are able to mutate an array into a heap, it can be proven that the time complexity is in fact O(n). The proof is given in the CLSR book referenced above. PriorityQueues heapify() uses the same algorithm. – Breathy

In the first paragraph you say, Each heapify() takes log(n) time. I understood that and the following discussion to mean you were speaking of the O(1) argument for inserting an item. I think my confusion comes from your use of the name heapify() to mean two different things (the function that builds the heap, and the function that's called by the build heap function). Changing that sentence to Each call to siftDown() takes log(n) time. It doesn't help that a lot of people use heapify() in place of siftDown(). I wish we could all agree on terminology. – Variegation

@JimMischel, Thanks for pointing out the more accurate terms. CLSR uses Max-Heapify and Build-Max-Heap and I didn't really think too much about it. I updated the answer with correct terms. – Breathy