Java PriorityQueue：如何使用自定义比较器堆化集合？

Question

例如，给定一个整数列表 List<Integer> list = Arrays.asList(5,4,5,2,2)，我怎样才能在 O(n) 时间复杂度内从这个列表中得到一个 maxHeap？

天真的方法：

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (Integer i : list) {
    maxHeap.offer(i);
}

但是，时间复杂度是O(nlogn)。

我们可以使用下面的构造函数来触发heapify方法：

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(list);

时间复杂度为O(n)。但是，它迫使我使用 自然顺序 即 minHeap.

我的问题：

如何通过使用自定义比较器堆化 Collection 来构造 PriorityQueue？

参考： Java doc of PriorityQueue

PS: @user207421
Heapify 算法可以在 O(n) 时间内将任何未排序的数组转换为堆，而不是 O(nlogn)。 There are many articles about heapify，同样在 CLRS 的算法导论第 159 页中，从任何未排序的数组构建堆是 O(n)。而且堆也不是排序数组。这是一棵完整的堆树属性，可以编码成数组。

Answer 1

如果你不介意一些技巧

根据java doc of PriorityQueue(PriorityQueue)

Creates a PriorityQueue containing the elements in the specified priority queue. This priority queue will be ordered according to the same ordering as the given priority queue.

所以我们可以将 PriorityQueue 扩展为 CustomComparatorPriorityQueue 来保存所需的比较器和我们需要堆化的集合。然后用 CustomComparatorPriorityQueue.

的实例调用 new PriorityQueue(PriorityQueue)

以下经过测试可在 Java 15.

中工作

import java.util.*;

public class CustomComparatorPriorityQueue<T> extends PriorityQueue<T> {
    private Collection<T> wrapped;

    public static <U> PriorityQueue<U> create(Collection<U> wrapped, Comparator<U> custom) {
        return new PriorityQueue<U>(new CustomComparatorPriorityQueue<>(wrapped, custom));
    }

    private CustomComparatorPriorityQueue(Collection<T> wrapped, Comparator<T> custom) {
        super(custom);
        this.wrapped = wrapped;
    }

    @Override
    public Object[] toArray() {
        return wrapped.toArray();
    }

    public static void main(String[] args) {
        List<Integer> a = Arrays.asList(3, 6, 4, 8, 1, 9);
        PriorityQueue<Integer> pq = CustomComparatorPriorityQueue.create(a, Comparator.<Integer>naturalOrder().reversed());
        Integer b;
        while ((b = pq.poll()) != null) {
            System.out.println(b);
        }
    }

    // Override to don't allow other purpose...
}

Answer 2

一种方法是通过最小堆实现最大堆：将集合中的每个数字乘以-1，然后将新集合堆化为最小堆，当我们从堆中检索数字时，也乘以- 1 获取原始数字。

Java PriorityQueue：如何使用自定义比较器堆化集合？

Java PriorityQueue: how to heapify a Collection with a custom Comparator?

java

heap

priority-queue

如果你不介意一些技巧