堆----3.数据流的中位数
295. 数据流的中位数 - 力扣（LeetCode）
/**
基础数据结构:
大顶堆:完全二叉树,任一结点>=其左右孩子;小顶堆:完全二叉树,任一结点<=其左右孩子
大体做法:
同时使用一个大顶堆与一个小顶堆,在插入元素时进行限制。
大顶堆元素最大值 <= 小顶堆元素最小值,且两堆元素相差个数不超过1
若两堆元素个数相等,则中位数:大顶堆堆顶元素(大顶堆最大值)与小顶堆堆顶元素(小顶堆最小值)的平均数
若大顶堆的元素更多,则中位数:大顶堆堆顶元素
若小顶堆的元素更多,则中位数:小顶堆堆顶元素(此处插入方式不存在该情况)
插入过程:
首先插入元素时统一直接插入大顶堆(小顶堆也可以)
再把大顶堆的堆顶元素(大顶堆最大元素)弹出,插入到小顶堆;(即先将元素插入大顶堆，再把大顶堆最大的元素移到小顶堆,实现了大顶堆元素最大值 <= 小顶堆元素最小值)
此时进行判断,若小顶堆元素更多,则将小顶堆堆顶元素(小顶堆最小元素)弹出,插入到大顶堆中;
(由于为了实现大顶堆元素最大值 <= 小顶堆元素最小值,将大顶堆的最大元素移到了小顶堆,此时必须要平衡两堆元素,否则元素会全部留在小顶堆中)
注意事项:
经过调整后要么两堆元素数量相等,要么大顶堆元素更多,不存在小顶堆元素更多的情况。
*/
/**基础数据结构:大顶堆:完全二叉树,任一结点>=其左右孩子;小顶堆:完全二叉树,任一结点<=其左右孩子大体做法:同时使用一个大顶堆与一个小顶堆,在插入元素时进行限制。大顶堆元素最大值 <= 小顶堆元素最小值,且两堆元素相差个数不超过1若两堆元素个数相等,则中位数:大顶堆堆顶元素(大顶堆最大值)与小顶堆堆顶元素(小顶堆最小值)的平均数若大顶堆的元素更多,则中位数:大顶堆堆顶元素若小顶堆的元素更多,则中位数:小顶堆堆顶元素(此处插入方式不存在该情况)插入过程:首先插入元素时统一直接插入大顶堆(小顶堆也可以)再把大顶堆的堆顶元素(大顶堆最大元素)弹出,插入到小顶堆;(即先将元素插入大顶堆，再把大顶堆最大的元素移到小顶堆,实现了大顶堆元素最大值 <= 小顶堆元素最小值)此时进行判断,若小顶堆元素更多,则将小顶堆堆顶元素(小顶堆最小元素)弹出,插入到大顶堆中;(由于为了实现大顶堆元素最大值 <= 小顶堆元素最小值,将大顶堆的最大元素移到了小顶堆,此时必须要平衡两堆元素,否则元素会全部留在小顶堆中)注意事项:经过调整后要么两堆元素数量相等,要么大顶堆元素更多,不存在小顶堆元素更多的情况。
*/
class MedianFinder {//大顶堆,左半区,存较小的元素private PriorityQueue<Integer> left_maxHeap;//小顶堆,右半区,存较大的元素private PriorityQueue<Integer> right_minHeap; public MedianFinder() {//优先队列实现大/小顶堆left_maxHeap = new PriorityQueue<>((a,b) -> b - a); //大顶堆,自定义比较器right_minHeap = new PriorityQueue<>(); //默认为小顶堆}public void addNum(int num) {//直接插入大顶堆left_maxHeap.offer(num);//保证 大顶堆元素最大值 <= 小顶堆元素right_minHeap.offer(left_maxHeap.poll());//平衡两堆元素个数 要么两堆元素个数相等,要么大顶堆比小丁堆多一个元素if(right_minHeap.size() > left_maxHeap.size()) {left_maxHeap.offer(right_minHeap.poll());}}public double findMedian() {//两堆元素相等 大顶堆堆顶元素(大顶堆最大值)与小顶堆堆顶元素(小顶堆最小值)的平均值if(right_minHeap.size() == left_maxHeap.size()) {return (right_minHeap.peek() + left_maxHeap.peek()) / 2.0;} //要么两堆元素个数相等,要么大顶堆比小顶堆多一个元素return left_maxHeap.peek();}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/