new 資料流中的中位數 大頂堆 小頂堆 測試未通過

如何得到一個資料流中的中位數？如果從資料流中讀出奇數個數值，那麼中位數就是所有數值排序之後位于中間的數值。如果從資料流中讀出偶數個數值，那麼中位數就是所有數值排序之後中間兩個數的平均值。我們使用Insert()方法讀取資料流，使用GetMedian()方法擷取目前讀取資料的中位數。

思路

由于資料是從一個資料流中讀出來的，而資料的數目随着時間的變化而增加，新的資料從流中讀出來，這些資料就插入資料容器。

不同的容器：

1、無序數組：快排

插入：O（1）

找出：O（n）

2、有序數組：

插入：O（n）

找出：O（1）

3、排序的連結清單

定義兩個連結清單指向中間節點，

插入：O（n）

找出：O（1）

4、二叉搜尋樹

插入：平均O(logn) 最差O（n）

找出：平均O(logn) 最差O（n）

5、AVL樹

平衡因子是左右子樹高度差，可以改為左右子節點數目差

插入：O(logn)

找出：O（1）

但程式設計者在短短幾十分鐘很難寫完。

6、最大堆和最小堆

插入：O(logn)

找出：O（1）

大頂堆、小頂堆

先用java集合PriorityQueue來設定一個小頂堆和大頂堆

主要的思想是：因為要求的是中位數，那麼這兩個堆，大頂堆用來存較小的數，從大到小排列；

小頂堆存較大的數，從小到大的順序排序*，顯然中位數就是大頂堆的根節點與小頂堆的根節點和的平均數。

⭐保證：小頂堆中的元素都大于等于大頂堆中的元素，是以每次塞值，并不是直接塞進去，而是從另一個堆中poll出一個最大（最小）的塞值

⭐當數目為偶數的時候，将這個值插入大頂堆中，再将大頂堆中根節點（即最大值）插入到小頂堆中；

⭐當數目為奇數的時候，将這個值插入小頂堆中，再講小頂堆中根節點（即最小值）插入到大頂堆中；

⭐取中位數的時候，如果目前個數為偶數，顯然是取小頂堆和大頂堆根結點的平均值；如果目前個數為奇數，顯然是取小頂堆的根節點

測試不通過：

import java.util.*; 
public class Solution {
    private PriorityQueue<Integer> minheap=new PriorityQueue<Integer>();
    private PriorityQueue<Integer> maxheap=new PriorityQueue<Integer>((x,y)->(y-x));
    int count=0;
    
    public void Insert(Integer num) {
        if(count % 2 == 0){
            maxheap.offer(num);
            int max=maxheap.poll();
            minheap.offer(max);
        }
        else
        {
            minheap.offer(num);
            int min=minheap.poll();
            maxheap.offer(min);
        }
        count++;
    }

    public Double GetMedian() {
        if(count % 2 == 0)
            return new Double (maxheap.poll()+minheap.poll())/2;
        else //((count&1)==1)
            return new Double (minheap.poll());
    }
}
           

測試通過：

import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
    //小頂堆
    private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
     
    //大頂堆
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });
     
    //記錄偶數個還是奇數個
    int count = 0;
    //每次插入小頂堆的是目前大頂堆中最大的數
    //每次插入大頂堆的是目前小頂堆中最小的數
    //這樣保證小頂堆中的數永遠大于等于大頂堆中的數
    //中位數就可以友善地從兩者的根結點中擷取了
    public void Insert(Integer num) {
        //個數為偶數的話，則先插入到大頂堆，然後将大頂堆中最大的數插入小頂堆中
        if(count % 2 == 0){
            maxHeap.offer(num);
            int max = maxHeap.poll();
            minHeap.offer(max);
        }else{
            //個數為奇數的話，則先插入到小頂堆，然後将小頂堆中最小的數插入大頂堆中
            minHeap.offer(num);
            int min = minHeap.poll();
            maxHeap.offer(min);
        }
        count++;
    }
    public Double GetMedian() {
        //目前為偶數個，則取小頂堆和大頂堆的堆頂元素求平均
        if(count % 2 == 0){
            return new Double(minHeap.peek() + maxHeap.peek())/2;
        }else{
            //目前為奇數個，則直接從小頂堆中取元素即可
            return new Double(minHeap.peek());
        }
    }
}
           

更簡便的方法：

用大頂堆+小頂堆方法，可以看作大頂堆是普通班，小頂堆是實驗班。數量上時刻保持 小頂-大頂<=1（兩堆相等或者小頂比大頂多一個）。

新學生先入普通班（大頂堆），此時可能會失去平衡了，于是取大頂堆的第一個（班裡最好的學生）加入實驗班（小頂堆），判斷若數量過多（不是等于或多一個），取第一個（實驗班裡最差的學生）到普通班（大頂堆）裡。 取中位數的時候，若兩堆數量相等，則各取堆頂取平均，若小頂比大頂多一，則多的那一個就是中位數。

class MedianFinder {
    PriorityQueue<Integer> left;//大頂
    PriorityQueue<Integer> right;//小頂
    public MedianFinder() {
        left=new PriorityQueue<>((n1,n2)->n2-n1);
        right=new PriorityQueue<>();
    }
    public void addNum(int num) {
        left.add(num);
        right.add(left.poll());
        if(left.size()+1<right.size())
            left.add(right.poll());
    }
    public double findMedian() {
        if(right.size()>left.size())return right.peek();
        return (double)(left.peek()+right.peek())/2;
    }
}