本文介紹了Java PriorityQueue：如何使用自定義比較器堆積集合？的處理方法，對(duì)大家解決問題具有一定的參考價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧！
問題描述
例如，給定一個(gè)整數(shù)列表List<Integer> list = Arrays.asList(5,4,5,2,2)，我如何在O(n)時(shí)間復(fù)雜度內(nèi)從該列表中獲得maxHeap？
天真的方法：
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (Integer i : list) {
maxHeap.offer(i);
}
但是，時(shí)間復(fù)雜度是O(nlogn)。
我們可以使用以下構(gòu)造函數(shù)觸發(fā)heapify方法：
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(list);
時(shí)間復(fù)雜度為O(n)。但是，它迫使我使用自然順序，即minHeap。
我的問題：
如何通過使用自定義比較器堆積集合來構(gòu)造PriorityQueue？
參考文獻(xiàn)：
Java doc of PriorityQueue
PS：
@user207421
Heapify算法可以在O(n)時(shí)間內(nèi)將任何未排序的數(shù)組轉(zhuǎn)換為堆，而不是O(nlogn)。There are many articles about heapify，同樣在CLRS的算法簡(jiǎn)介第159頁(yè)中，從任何未排序的數(shù)組構(gòu)建堆是O(n)。而heap也不是排序數(shù)組。它是一個(gè)完整的樹，具有堆屬性，可以在數(shù)組中編碼。
推薦答案
如果您不介意黑客攻擊
根據(jù)java doc of PriorityQueue(PriorityQueue)
創(chuàng)建包含指定優(yōu)先級(jí)隊(duì)列中的元素的PriorityQueue。此優(yōu)先級(jí)隊(duì)列將按照與給定優(yōu)先級(jí)隊(duì)列相同的順序進(jìn)行排序。
因此我們可以擴(kuò)展PriorityQueueAsCustomComparatorPriorityQueue以保存所需的比較器和我們需要堆積的集合。然后使用CustomComparatorPriorityQueue的實(shí)例調(diào)用newPriorityQueue(PriorityQueue)。
下面的測(cè)試可以在Java 15中運(yùn)行。
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...
}
這篇關(guān)于Java PriorityQueue：如何使用自定義比較器堆積集合？的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，
