CODEWITHSUNDEEP
javapriority-queuemin-heap
rainyday
rainyday

Reputation: 383

create PriorityQueue in O(n ) with custom comparator

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;
            }
        }
    });

Upvotes: 6

Views: 1835

Answers (2)

jrook
jrook

Reputation: 3519

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.

Upvotes: 3

corsiKa
corsiKa

Reputation: 82559

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);

Upvotes: 4

Related Questions