Java PriorityQueue：如何使用自定义比较器堆积集合-Java问题

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

本文介绍了Java PriorityQueue：如何使用自定义比较器堆积集合？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

例如，给定一个整数列表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 PriorityQueue create(Collection wrapped, Comparator custom) { return new PriorityQueue(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：如何使用自定义比较器堆积集合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！