Java 优先队列堆化

Question

一般来说，如果我理解正确的话，“heapifying;o(n)”给定列表与添加每个单独元素之间的运行时间是不同的； o(lgn)。 java 是否遵循此行为？如果不是以下问题可能无效。

下面的示例似乎创建了一个“最小堆”。

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

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

 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

However, let say if I want to build a "max heap", but the constructor does not let me pass in a collection and comparator together. In this case, is the only to build max heap is via creating a wrapper class that implements comparable?

是的。这个class没有提供可以同时传入一个collection和一个comparator的构造函数。它将使用集合元素的compareTo方法，所以像你一样，你需要一个Wrapper（但这似乎有点不必要？）。

repeatedly call add.

您可以使用 PriorityQueue#addAll().

Answer 2

来自 java 文档：

The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at QUEUE CONSTRUCTION TIME, depending on which constructor is used https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

所以你必须在构建队列时提供排序策略。假设您正在尝试拥有最大堆（以相反的方式排序），那么队列构造将如下所示：-

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

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

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

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

像这样：

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

Java 优先队列堆化

Java Priority Queue heapify

java

priority-queue