在Java中以O（N）而非O（NlogN）的时间复杂度构建堆

Question

在Java中以O（N）而非O（NlogN）的时间复杂度构建堆

3

要构建堆，我们可以使用Java中的PriorityQueue类。是否有一种使用内置库/类直接从数组中以O(N)的时间复杂度构建堆的方法，而不是将每个元素单独推入以O(NlogN)的时间复杂度构建堆？

- Zephyr

3

@Razib，不，这不是一个重复的问题。在Java中，我们不能一次性将整个数组取出并在O（n）时间内构建堆（据我所知）。我们必须单独将数组的每个元素插入堆中，这需要O（NlogN）的时间。所以我的问题是，有没有一种方法可以在O（N）时间内获取整个数组并构建堆？我非常清楚从数组构建堆所需的时间复杂度为O（N）。 - Zephyr

我投票支持重新开放，因为标记的重复说明了它在计算上是可能的，而不是如何使用Java内置的PriorityQueue实现。 - that other guy

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- that other guy · Accepted Answer

使用接受集合的构造函数：

new PriorityQueue<String>(Arrays.asList(yourArray));

Java文档一贯地没有提到复杂度的任何内容，但是阅读源代码显示，OpenJDK使用了典型的O(n)堆化方法，而不是在循环中插入：

private void initFromCollection(Collection<? extends E> c) {
    initElementsFromCollection(c);
    heapify();
}