本文介紹了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ò)展PriorityQueue
AsCustomComparatorPriorityQueue
以保存所需的比較器和我們需要堆積的集合。然后使用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ì)大家有所幫助,