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

Question

例如，给定一个整数列表 List<Integer> list = Arrays.asList(5,4,5,2,2) , 我怎样才能得到一个 maxHeap来自此列表 O(n)时间复杂度？
幼稚的方法:

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) .但是，它迫使我使用 自然秩序这是 最小堆 .
我的问题:
如何通过使用自定义比较器堆化集合来构建 PriorityQueue？
引用:
Java doc of PriorityQueue
PS:
@用户207421
Heapify 算法可以将任何未排序的数组转换为堆 O(n)时间，而不是 O(nlogn) . There are many articles about heapify .堆也不是排序数组。它是一个具有堆属性的完整树，可以在数组中进行编码。

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保存所需的比较器和我们需要堆化的集合。然后拨打新的 PriorityQueue(PriorityQueue)带有 CustomComparatorPriorityQueue 的实例.
下面经过测试可以在 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...
}