還記得Java優先佇列嗎，進來復習復習..
Java中優先佇列默認是小根堆，堆頂元素即佇列最小值，
在很多應用中，我們通常需要按照優先級情況對待處理物件進行處理，比如首先處理優先級最高的物件，然后處理次 高的物件，最簡單的一個例子就是，在手機上玩游戲的時候，如果有來電，那么系統應該優先處理打進來的電話， 在這種情況下，我們的資料結構應該提供兩個最基本的操作，一個是回傳最高優先級物件，一個是添加新的物件，這 種資料結構就是優先級佇列(Priority Queue)，
來實戰：
題目描述：
代碼實作：
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] res = new int[k]; //結果集
if (k == 0) return res;
PriorityQueue<Integer> pq = new PriorityQueue<>(k,new Comparator<Integer>(){
public int compare(Integer o1,Integer o2) {
return o2 - o1;
} //Java默認小根堆，更改排序方法為小根堆
});
for (int i = 0;i < arr.length;i++) {
if (i < k) {
pq.add(arr[i]); //先將前k個元素入隊
} else {
if (arr[i] < pq.peek()) {
pq.poll();
pq.add(arr[i]); //比堆頂元素大的元素存放進來
}
}
}
for (int i = 0;i < k;i++) {
res[i] = pq.poll();
}
return res;
}
}使用優先佇列還有一個還出就是隨時可以添加新元素，而不需要重新排序，只要將新元素與堆頂元素做一次比較即可，
比如這題：
資料流中的中位數
這題是要求實作隨時添加元素之后求出中位數，同樣可以采用優先佇列解決，將一組資料分為兩段，比中位數小的為前半段，升序排序，即大根堆，堆頂元素就是中位數；比中位數大的為后半段，建立小根堆，堆頂元素就是最小的，也是中位數或者中位數右邊元素，所以這里要判斷陣列長度是奇數還是偶數，長度是偶數則添加元素時添加到前半段，這樣前半段的最大值（堆頂元素）就是中位數，長度為奇數時，根據前面操作，前半段的陣列長度比后半段大1，添加元素添加到后半段，中位數是兩個堆頂元素和的二分之一，當然，添加元素時不能直接添加，因為要保證陣列整體有序，所以要先到另一個堆里過濾一遍，挑出最大或者最小的元素添加，
代碼實作如下：
class MedianFinder {
PriorityQueue<Integer> max,min;
/** initialize your data structure here. */
public MedianFinder() {
max = new PriorityQueue<>((o1,o2) -> (o2 - o1));//大根堆，保存較小的一半
min = new PriorityQueue<>();//小根堆，保存加大的一半
}
public void addNum(int num) {
if (max.size() == min.size()) { //偶數，添加元素到前半段
min.offer(num); //先拿到后半段過濾，找到最小值再將最小值添加到前半段，保證整體有序
max.offer(min.poll());
} else { //奇數，添加元素到后半段
max.offer(num); //拿到前半段過濾，找到最大值添加到后半段，保證整體有序
min.offer(max.poll());
}
}
public double findMedian() {
return max.size() > min.size() ? max.peek() : (max.peek() + min.peek()) / 2.0;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/384422.html
標籤：其他