o)

5ktev3wc 于 2021-07-07 发布在 Java

关注(0)|答案(1)|浏览(456)

从priorityqueue javadoc：
实现说明：此实现为排队和出列方法提供了o（log（n））时间 offer , poll , remove() 以及 add ; 线性时间 remove(Object) 以及 contains(Object) 方法；检索方法的时间常数 peek , element ，和 size .
所以，我的问题是，o（log（n））的时间复杂度是否适合合并 PriorityQueue 把她变成一个？或者是o（nlog（n））考虑插入？如果合并更多堆，这种情况会改变吗？
这些 PriorityQueue s代表堆。
像这样：

PriortityQueue<Integer> a = new PriorityQueue<>();
... add elements
PriortityQueue<Integer> b = new PriorityQueue<>();
... add elements
PriorityQueue<Integer> merged = new PriorityQueue<>(a.size() + b.size(), a.comparator()); // Assuming a and b have the same Comparator.
merged.addAll(a);
merged.addAll(b);

Java heap priority-queue big-o time-complexity

来源：https://stackoverflow.com/questions/65094758/time-complexity-big-o-of-merging-two-priorityqueues

1条答案

按热度按时间

ryoqjall1#

正如你所指出的方法 add 来自班级 PriorityQueue 有 O(log(N)) 时间复杂性。如果你看看这个方法的具体实现 addAll 来自班级 PriorityQueue ，您将看到以下内容：

public boolean addAll(Collection<? extends E> c) {
    if (c == null)
        throw new NullPointerException();
    if (c == this)
        throw new IllegalArgumentException();
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}

因此，对于作为参数传递的集合中的每个元素 add 被称为。因此，最终的复杂性将是 O(Mlog(N)) ，在哪里 M 作为参数和参数传递的集合的元素数 N 优先级队列的元素数。

赞(0）回复(0）举报 2021-07-07

我来回答

o)

1条答案

相关问题

热门标签

最新问答