每日写题分享–优先队列
还记得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;
}
}