Java优先级队列构建堆进程时间复杂性

Question

构建堆的时间复杂度为O（n）。问题是Java优先级队列是否可以实现它？让我们举一个例子：

ArrayList<Integer> list=new ArrayList<Integer>(Arrays.asList(5,6,7,0,1,33));
Queue<Integer> queue=new PriorityQueue<Integer>(list); // Seems O(n) if it uses efficient build heap

while(!queue.isEmpty()) {
    System.out.println(queue.poll()); //log(n)
}

...

现在我们可以看到，它将按照自然顺序进行排序，即递增顺序。Java没有一个构造函数既接受列表又接受比较器。如果我想创建Max Heap，则如下所示：

...

ArrayList<Integer> list=new ArrayList<Integer>(Arrays.asList(5,6,7,0,1,33));
Queue<Integer> queue=new PriorityQueue<Integer>(new Comparator<Integer>() {
    @Override
    public int compare(Integer arg0, Integer arg1) {
        return arg1.compareTo(arg0);
    }});
for(Integer val:list) {
    queue.offer(val);
}
// nlog(n) in above for loop. Can't use build heap
while(!queue.isEmpty()) {
    System.out.println(queue.poll());
}

...

如果我想使用PriorityQueue对自定义类进行排序，那么它将永远无法实现构建堆O（n）。或者我们可以吗？

Answer 1

当我运行以下程序时

System.out.println("Elements    Via constructor      Via offer()");
System.out.println("               Add Then-remove       Add Then-remove");

for(int size: new int[] { 10, 100, 1_000, 10_000, 100_000, 1_000_000 }) {
    int[] comparisons = { 0 };
    class Element implements Comparable<Element> {
        int x;
        Element(int x) { this.x = x; }
        public int compareTo(Element o) {comparisons[0]++;return Integer.compare(x,o.x);}
        @Override public String toString() { return String.valueOf(x); }
    }
    List<Element> samples = IntStream.range(0, size)
        .mapToObj(Element::new)
        .collect(Collectors.toCollection(ArrayList::new));
    Collections.shuffle(samples, ThreadLocalRandom.current());

    System.out.printf("%8d", samples.size());

    PriorityQueue<Element> q1 = new PriorityQueue<>(samples);
    System.out.printf("%10d", comparisons[0]);
    comparisons[0] = 0;
    while(!q1.isEmpty()) q1.remove();
    System.out.printf("%12d", comparisons[0]);

    comparisons[0] = 0;
    PriorityQueue<Element> q2 = new PriorityQueue<>(Comparator.naturalOrder());
    for(Element e: samples) q2.offer(e);
    System.out.printf("%10d", comparisons[0]);
    comparisons[0] = 0;
    while(!q2.isEmpty()) q2.remove();
    System.out.printf("%12d", comparisons[0]);
    System.out.println();
}

我反复得到的结果是

Elements    Via constructor      Via offer()
               Add Then-remove       Add Then-remove
      10        13          27        13          27
     100       169         850       205         850
    1000      1863       14949      2264       14947
   10000     18820      216653     22696      216736
  100000    188046     2831466    228471     2831779
 1000000   1881455    34913307   2281512    34914028

显示通过offer添加元素确实会执行更多比较，但仍然具有O（n）时间复杂性。由于检索元素表现出O（n logn）复杂性，因此它使结构上的差异变得微不足道。

进一步注意，如果没有洗牌，即使用预先排序的数据，两种方法之间根本没有区别。实际上，数据可能介于排序和完全随机之间。

所以对大多数实际目的来说，答案是这并不重要。

如果你真的需要在受控环境中挤出最大的性能，你可以使用黑客：

Comparator<Element> comparator = Comparator.naturalOrder();
PriorityQueue<Element> q = new PriorityQueue<>(
    new PriorityQueue<>(comparator) { // not really recommended
        @Override
        public Object[] toArray() {
            return samples.toArray();
        }
    });

PriorityQueue将从输入PriorityQueue中获取比较器，但是当getClass（）时，不会信任toArray（）结果中元素的顺序！=PriorityQueue.class，如本例所示，并返回到将任意集合传递给构造函数时使用的相同例程。最终结果是设置比较器和使用任意集合输入初始化的行为。

当然，对于您计划提供给其他人的任何代码，都不建议依赖这些实现细节。但除非将来的版本添加PriorityQueue（集合

但正如本答案的第一部分所示，您可能无论如何都不需要这种破解，因为通过offer添加所有元素也具有合理的性能。