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

*PriorityQueue.addAll() ... is O(nlogn) method*. Do you have any evidence for this? — jrook, Nov 02 '17 at 17:57
Actually I am confused with accepted answer of this post. https://stackoverflow.com/questions/34693414/what-is-the-time-complexity-of-constructing-a-priorityqueue-from-a-collection — rainyday, Nov 02 '17 at 17:57
@rainyday I was incorrect that you cannot create it in `O(n)` time from scratch... been a while since I was in Data Structures!! :) — corsiKa, Nov 02 '17 at 18:10
@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). — Jim Mischel, Nov 02 '17 at 20:54
@jrook 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. — corsiKa, Nov 02 '17 at 23:12

corsiKa · Accepted Answer · 2017-11-02T18:28:45.837

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

jrook · Answer 2 · 2017-11-03T01:13:57.950

3

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.

edited Nov 03 '17 at 01:13

answered Nov 02 '17 at 18:04

jrook

3,459
1
16
33

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... – corsiKa Nov 02 '17 at 18:08
@corsiKa, you are right. But won't that be fixed by implementing `compareTo()` for the object contained in the collection? – jrook Nov 02 '17 at 18:20
1

Yes, that's a possibility - OP may or may not be able to control that - although he could compose a container class? – corsiKa Nov 02 '17 at 18:24
1

@jrook will that work for PriorityQueue for natural ordering ? – rainyday Nov 02 '17 at 18:38
@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. – jrook Nov 02 '17 at 18:47
@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. – jrook Nov 02 '17 at 18:52
Whereas the O(1) argument (see https://stackoverflow.com/questions/39514469/argument-for-o1-average-case-complexity-of-heap-insertion) 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. – Jim Mischel Nov 02 '17 at 21:35
@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. `PriorityQueue`s `heapify()` uses the same algorithm. – jrook Nov 02 '17 at 21:44
1

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. – Jim Mischel Nov 02 '17 at 22:13
@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. – jrook Nov 02 '17 at 22:33

create PriorityQueue in O(n ) with custom comparator

2 Answers2