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

Question

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

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

引用：PriorityQueue的Java文档

ps:@user207421
Heapify算法可以在O(n)时间内将任何未排序的数组转换为堆，而不是O(nlogn)。有很多关于Heapify的文章。堆也不是排序数组。它是一个具有堆属性的完整树，可以用数组进行编码。

Answer 1

根据PriorityQueue（PriorityQueue）的java文档

创建包含指定优先级队列中的元素的PriorityQueue。此优先级队列将按照与给定优先级队列相同的顺序进行排序。

因此，我们可以将PriorityQueue扩展为CustomComparatorPriorityQueue，以保存所需的比较器和需要heapify的集合。然后使用CustomComparatorPriorityQueue实例调用新的PriorityQueue(PriorityQueue)。

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...
}