本文介紹了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 <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：如何使用自定義比較器堆積集合？的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，
