6

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

2 回答 2

4

如果您没有在其他地方对您的列表进行最小堆排序，那么您将无法做new PriorityQueue(...)任何事情并以某种方式避免创建堆的影响。这里的数学表示它是O(n)针对一般情况的，但它仍然不仅仅是迭代。

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!!!
    }
}

现在我还没有对此进行测试，它只是在 PriorityQueue 源的一些指导下我的头脑，但它应该指向正确的方向。

但有时你必须付钱给 piper 并创建堆顺序，而这不仅仅是迭代。它应该仍然打开O(n)，因为heapify.

另一种选择是edge实施Comparable<edge>. 然后你可以PriorityQueue<edge> pr = new PriorityQueue(ar);

如果您无法控制edge implements Comparable<edge>，那么您可以编写一个容器类：

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);
于 2017-11-02T17:59:28.077 回答
3

JavaPriorityQueue需要 O(n) 时间从传递给它的集合中创建优先级队列。数学证明已在 CLSR 第 6.4 章（第 3 版第 157 页）中给出。siftDown直观地说，随着使用or将底层数组突变为堆siftUp，为下一个操作循环的元素数量的大小sift也会减小，从而导致 O(n) 时间复杂度。

但是正如评论中所讨论的以及您在问题中提到的那样，您无法通过使用来实现这种时间复杂度addAll()。原因是adAll()继承自AbstractQueue并通过将集合中的元素一一添加到队列中来工作，这可能导致 O(nlogn) 时间复杂度。

因此，如果绝对要求具有 O(n) 时间复杂度，那么您将别无选择，只能Comparator为集合中包含的对象类实现接口。@corsiKa 的回答很好地详细说明了这种方法。另请注意，即使您将集合直接传递给PriorityQueue，它也会将其转换为数组，这基本上是另一个 O(n) 操作。

于 2017-11-02T18:04:34.773 回答