在 Java 中以 O(N) 而不是 O(NlogN) 构建堆

Question

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

Answer 1

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

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

诚然，Java Docs 没有提及任何关于复杂性的内容，但阅读源代码表明 OpenJDK 使用典型的O(n)heapify 方法而不是插入循环：

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