相关疑难解决方法(0)

要构建最大堆树,我们可以siftDown或siftUp通过筛选下来,我们从根开始,并将它与它的两个孩子,那么我们有两个孩子的更大的元素替换它,如果这两个孩子是小然后我们停下来,否则我们继续筛选那个元素直到我们到达一个叶子节点(或者当然再次,直到该元素大于它的两个子节点).

现在我们只需要做那些n/2时间,因为叶子的数量是n/2,当我们完成堆积最后一个元素(在叶子之前)之前的水平上时叶子将满足堆属性 - 所以我们将留下n/2要堆积的元素.

现在,如果我们使用siftUp,我们将从叶子开始,最终我们将需要堆积所有n元素.

我的问题是:当我们使用时,我们siftDown不是基本上进行两次比较(将元素与其两个子元素进行比较),而不是在使用时只进行一次比较siftUp,因为我们只将该元素与其父元素进行比较？如果是的话,那是不是意味着我们将复杂性提高一倍并最终达到与筛选相同的复杂性？

我试图用自定义比较器实现带有Priorityqueue的MST,但是我在O(n)时间内用它构建min-heap时遇到了问题.问题是,Priorityqueue的一个构造函数只允许在O(n)中创建PriorityQueue,但它不会将任何比较器作为参数.我希望它使用我的自定义比较器.这个问题有解决方法吗？PriorityQueue.addAll()将失去使用Min-heap作为MST的目的,因为它是O(nlogn)方法.这是我的代码.

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

我要使用的比较器: -

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

为了构建堆，我们使用 java 中的 PriorityQueue 类。有没有办法使用内置库/类直接从 O(N) 中的数组构建堆，而不是单独推送每个元素以在 O(NlogN) 中构建堆？