Java PriorityQueue：如何使用自定义比较器堆积集合？ [英] Java PriorityQueue: how to heapify a Collection with a custom Comparator?

问题描述

例如，给定一个整数列表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。

我的问题：

如何通过使用自定义比较器堆积集合来构造PriorityQueue？

参考文献： Java doc of PriorityQueue

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

推荐答案

如果您不介意黑客攻击

根据java doc of PriorityQueue(PriorityQueue)

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

因此我们可以扩展PriorityQueueAsCustomComparatorPriorityQueue以保存所需的比较器和我们需要堆积的集合。然后使用CustomComparatorPriorityQueue的实例调用newPriorityQueue(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...
}

这篇关于Java PriorityQueue：如何使用自定义比较器堆积集合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！