本文主要是介绍PriorityQueue 总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Find Median from Data Stream 用两个堆来维持关系，左边用最大堆，右边用最小堆，如果num[i] 比最大堆的堆顶小，加入最大堆，否则加入最小堆，然后再调整数目，始终保证最大堆比最小堆数目相等，或者只大于1；
class MedianFinder {private PriorityQueue<Integer> maxheap;private PriorityQueue<Integer> minheap;/** initialize your data structure here. */public MedianFinder() {maxheap = new PriorityQueue<Integer>((a, b) -> (b - a));minheap = new PriorityQueue<Integer>();}public void addNum(int num) {if(maxheap.isEmpty() || num < maxheap.peek()) {maxheap.add(num);} else {minheap.add(num);}balance();}private void balance() {while(maxheap.size() < minheap.size()) {maxheap.add(minheap.poll());}while(minheap.size() < maxheap.size() - 1) {minheap.add(maxheap.poll());}}public double findMedian() {if(maxheap.size() == minheap.size()) {return 0.5 * ((double)maxheap.peek() + (double)minheap.peek());} else {return (double)maxheap.peek();}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/Sliding Windom Median 跟 Find Median from Data Stream类似，用maxheap minheap去维持中位数，不同的地方就是window移动的时候，需要把头部的元素给去掉，注意后面一定要再balance一下；注意balance的时候，minheap.size() < maxheap.size() - 1，不能忍；注意，double的maxheap，不能用(a , b) ->(b - a)，一定要用Collections.reverseOrder();
class Solution {private PriorityQueue<Integer> maxheap, minheap;public double[] medianSlidingWindow(int[] nums, int k) {maxheap = new PriorityQueue<Integer>(k / 2 + 1, Collections.reverseOrder());minheap = new PriorityQueue<Integer>(k / 2 + 1);List<Double> list = new ArrayList<>();for(int i = 0; i < nums.length; i++) {if(maxheap.isEmpty() || nums[i] <= maxheap.peek()) {maxheap.add(nums[i]);} else {minheap.add(nums[i]);}balance();if(i == k - 1) {list.add(getMedian());}if(i > k - 1) {remove(nums[i - k]);balance();list.add(getMedian());}}// convert list to res;double[] res = new double[list.size()];for(int i = 0; i < res.length; i++) {res[i] = list.get(i);}return res;}private double getMedian() {if(maxheap.size() == minheap.size()) {return 0.5 * ((double) maxheap.peek() + (double) minheap.peek());} else {return (double)maxheap.peek();}}private void balance() {if(maxheap.size() < minheap.size()) {maxheap.add(minheap.poll());}if(minheap.size() < maxheap.size() - 1) {minheap.add(maxheap.poll());}}private void remove(int num) {if(num <= maxheap.peek()) {maxheap.remove(num);} else {minheap.remove(num);}}
}这篇关于PriorityQueue 总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
