Java优先级队列heapify[重复]

Question

一般来说，如果我理解正确的话，在给定列表和添加每个元素之间的“heapizing；o（n）”运行时是有区别的；o（lg n）。java遵循这种行为吗？如果不是，下面的问题可能无效。

下面的示例似乎创建了一个"min-heap"。

List<Integer> myList = List.of(4,3,10,1);
PriorityQueue<Integer> queue = new PriorityQueue<>(myList);

然而，假设我想构建一个“最大堆”，但是构造函数不允许我同时传入集合和比较器。在这种情况下，构建最大堆的唯一方法是创建一个实现可比的包装器类吗？

 class Wrapper implements Comparable<Wrapper> {
 ...
 @Override
 int compareTo(Wrapper o) {// define rule here...}
 }

 List<Integer> val = List.of(5,3,2,10);
 List<Wrapper> wrappedVal = val.stream().map(Wrapper::new).collect(Collectors.toList());

 PriorityQueue<Wrapper> queue = new PriorityQueue<>(wrappedVal); 

注意：我知道可以用比较器创建优先级队列，然后重复调用add。

Answer 1

从java文档：

优先级队列的元素根据其自然顺序排序，或者根据使用的构造函数，由QUEUE CONSTRUCTION Time提供的比较器排序https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

因此，您必须在构建队列时提供订购策略。假设您试图拥有max-heap（以反向方式排序），那么队列构建将如下所示：-

Queue<Integer> queue = new PriorityQueue<>(new YourCustomComparator())

或者，如果你只是处理整数，你可以利用自定义的：

Queue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

这一步只是创建队列。现在如何添加元素？这里有各种可用的方法签名。假设您有可用的列表，那么您可以简单地将它们传递给addAll方法。

比如：

 queue.addAll(List.of(5, 3, 2, 10));

Answer 2

然而，假设我想构建一个“最大堆”，但是构造函数不允许我同时传入集合和比较器。在这种情况下，构建最大堆的唯一方法是创建一个实现可比的包装器类吗？

是的。此类不提供可以同时传入集合和比较器的构造函数。它将使用集合元素的compareTo方法，所以正如您所做的那样，您需要一个Wrapper（但这似乎有点不必要？）。

反复呼叫add。

您可以使用PriorityQueue#addAll（）。