數(shù)據(jù)流中的中位數(shù)

題目：如何得到一個數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值，那么中位數(shù)就是所有值排序之后位于中間的數(shù)值。如果數(shù)據(jù)流中讀出偶數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值。

解題思路

由于數(shù)據(jù)是從一個數(shù)據(jù)流中讀出來的，數(shù)據(jù)的數(shù)目隨著時間的變化而增加。如果用一個數(shù)據(jù)容器來保存從流中讀出來的數(shù)據(jù)，當有新的數(shù)據(jù)流中讀出來時，這些數(shù)據(jù)就插入到數(shù)據(jù)容器中。這個數(shù)據(jù)容器用什么數(shù)據(jù)結構定義更合適呢？

數(shù)組是最簡單的容器。如果數(shù)組沒有排序，可以用 Partition 函數(shù)找出數(shù)組中的中位數(shù)。在沒有排序的數(shù)組中插入一個數(shù)字和找出中位數(shù)的時間復雜度是 O(1)和 O(n)。

我們還可以往數(shù)組里插入新數(shù)據(jù)時讓數(shù)組保持排序，這是由于可能要移動 O(n)個數(shù)，因此需要 O(n)時間才能完成插入操作。在已經(jīng)排好序的數(shù)組中找出中位數(shù)是一個簡單的操作，只需要 O(1)時間即可完成。

排序的鏈表時另外一個選擇。我們需要 O(n)時間才能在鏈表中找到合適的位置插入新的數(shù)據(jù)。如果定義兩個指針指向鏈表的中間結點（如果鏈表的結點數(shù)目是奇數(shù)，那么這兩個指針指向同一個結點），那么可以在 O（1）時間得出中位數(shù)。此時時間效率與及基于排序的數(shù)組的時間效率一樣。

二叉搜索樹可以把插入新數(shù)據(jù)的平均時間降低到 O(logn)。但是，當二叉搜索樹極度不平衡從而看起來像一個排序的鏈表時，插入新數(shù)據(jù)的時間仍然是 O(n)。為了得到中位數(shù)，可以在二叉樹結點中添加一個表示子樹結點數(shù)目的字段。有了這個字段，可以在平均 O(logn)時間得到中位數(shù)，但差情況仍然是 O(n)。

為了避免二叉搜索樹的最差情況，還可以利用平衡的二叉搜索樹，即 AVL 樹。通常 AVL 樹的平衡因子是左右子樹的高度差。可以稍作修改，把 AVL 的平衡因子改為左右子樹結點數(shù)目只差。有了這個改動，可以用 O(logn)時間往 AVL 樹中添加一個新結點，同時用 O(1)時間得到所有結點的中位數(shù)。

AVL 樹的時間效率很高，但大部分編程語言的函數(shù)庫中都沒有實現(xiàn)這個數(shù)據(jù)結構。應聘者在短短幾十分鐘內實現(xiàn) AVL 的插入操作是非常困難的。于是我們不得不再分析還有沒有其它的方法。

如果能夠保證數(shù)據(jù)容器左邊的數(shù)據(jù)都小于右邊的數(shù)據(jù)，這樣即使左、右兩邊內部的數(shù)據(jù)沒有排序，也可以根據(jù)左邊最大的數(shù)及右邊最小的數(shù)得到中位數(shù)。如何快速從一個容器中找出最大數(shù)？用最大堆實現(xiàn)這個數(shù)據(jù)容器，因為位于堆頂?shù)木褪亲畲蟮臄?shù)據(jù)。同樣，也可以快速從最小堆中找出最小數(shù)。　　因此可以用如下思路來解決這個問題：用一個最大堆實現(xiàn)左邊的數(shù)據(jù)容器，用最小堆實現(xiàn)右邊的數(shù)據(jù)容器。往堆中插入一個數(shù)據(jù)的時間效率是 O(logn)。由于只需 O(1)時間就可以得到位于堆頂?shù)臄?shù)據(jù)，因此得到中位數(shù)的時間效率是 O(1)。

接下來考慮用最大堆和最小堆實現(xiàn)的一些細節(jié)。首先要保證數(shù)據(jù)平均分配到兩個堆中，因此兩個堆中數(shù)據(jù)的數(shù)目之差不能超過 1（為了實現(xiàn)平均分配，可以在數(shù)據(jù)的總數(shù)目是偶數(shù)時把新數(shù)據(jù)插入到最小堆中，否則插入到最大堆中）。

還要保證最大堆中里的所有數(shù)據(jù)都要小于最小堆中的數(shù)據(jù)。當數(shù)據(jù)的總數(shù)目是偶數(shù)時，按照前面分配的規(guī)則會把新的數(shù)據(jù)插入到最小堆中。如果此時新的數(shù)據(jù)比最大堆中的一些數(shù)據(jù)要小，怎么辦呢？

可以先把新的數(shù)據(jù)插入到最大堆中，接著把最大堆中的最大的數(shù)字拿出來插入到最小堆中。由于最終插入到最小堆的數(shù)字是原最大堆中最大的數(shù)字，這樣就保證了最小堆中的所有數(shù)字都大于最大堆中的數(shù)字。 當需要把一個數(shù)據(jù)插入到最大堆中，但這個數(shù)據(jù)小于最小堆里的一些數(shù)據(jù)時，這個情形和前面類似。

輔助類實現(xiàn)

堆實現(xiàn)

private static class Heap<T> {
    // 堆中元素存放的集合
    private List<T> data;
    // 比較器
    private Comparator<T> cmp;
    /**
     * 構造函數(shù)
     *
     * @param cmp 比較器對象
     */
    public Heap(Comparator<T> cmp) {
        this.cmp = cmp;
        this.data = new ArrayList<>(64);
    }
    /**
     * 向上調整堆
     *
     * @param idx 被上移元素的起始位置
     */
    public void shiftUp(int idx) {
        // 檢查是位置是否正確
        if (idx < 0 || idx >= data.size()) {
            throw new IllegalArgumentException(idx + "");
        }
        // 獲取開始調整的元素對象
        T intent = data.get(idx);
        // 如果不是根元素，則需要上移
        while (idx > 0) {
            // 找父元素對象的位置
            int parentIdx = (idx - 1) / 2;
            // 獲取父元素對象
            T parent = data.get(parentIdx);
            //上移的條件，子節(jié)點比父節(jié)點大，此處定義的大是以比較器返回值為準
            if (cmp.compare(intent, parent) > 0) {
                // 將父節(jié)點向下放
                data.set(idx, parent);
                idx = parentIdx;
                // 記錄父節(jié)點下放的位置
            }
            // 子節(jié)點不比父節(jié)點大，說明父子路徑已經(jīng)按從大到小排好順序了，不需要調整了
            else {
                break;
            }
        }
        // index此時記錄是的最后一個被下放的父節(jié)點的位置（也可能是自身），
        // 所以將最開始的調整的元素值放入index位置即可
        data.set(idx, intent);
    }
    /**
     * 向下調整堆
     *
     * @param idx 被下移的元素的起始位置
     */
    public void shiftDown(int idx) {
        // 檢查是位置是否正確
        if (idx < 0 || idx >= data.size()) {
            throw new IllegalArgumentException(idx + "");
        }
        // 獲取開始調整的元素對象
        T intent = data.get(idx);
        // 獲取開始調整的元素對象的左子結點的元素位置
        int leftIdx = idx * 2 + 1;
        // 如果有左子結點
        while (leftIdx < data.size()) {
            // 取左子結點的元素對象，并且假定其為兩個子結點中最大的
            T maxChild = data.get(leftIdx);
            // 兩個子節(jié)點中最大節(jié)點元素的位置，假定開始時為左子結點的位置
            int maxIdx = leftIdx;
            // 獲取右子結點的位置
            int rightIdx = leftIdx + 1;
            // 如果有右子結點
            if (rightIdx < data.size()) {
                T rightChild = data.get(rightIdx);
                // 找出兩個子節(jié)點中的最大子結點
                if (cmp.compare(rightChild, maxChild) > 0) {
                    maxChild = rightChild;
                    maxIdx = rightIdx;
                }
            }
            // 如果最大子節(jié)點比父節(jié)點大，則需要向下調整
            if (cmp.compare(maxChild, intent) > 0) {
                // 將較大的子節(jié)點向上移
                data.set(idx, maxChild);
                // 記錄上移節(jié)點的位置
                idx = maxIdx;
                // 找到上移節(jié)點的左子節(jié)點的位置
                leftIdx = 2 * idx + 1;
            }
            // 最大子節(jié)點不比父節(jié)點大，說明父子路徑已經(jīng)按從大到小排好順序了，不需要調整了
            else {
                break;
            }
        }
        // index此時記錄是的最后一個被上移的子節(jié)點的位置（也可能是自身），
        // 所以將最開始的調整的元素值放入index位置即可
        data.set(idx, intent);
    }
    /**
     * 添加一個元素
     *
     * @param item 添加的元素
     */
    public void add(T item) {
        // 將元素添加到最后
        data.add(item);
        // 上移，以完成重構
        shiftUp(data.size() - 1);
    }
    /**
     * 刪除堆頂結點
     *
     * @return 堆頂結點
     */
    public T deleteTop() {
        // 如果堆已經(jīng)為空，就拋出異常
        if (data.isEmpty()) {
            throw new RuntimeException("The heap is empty.");
        }
        // 獲取堆頂元素
        T first = data.get(0);
        // 刪除最后一個元素
        T last = data.remove(data.size() - 1);
        // 刪除元素后，如果堆為空的情況，說明刪除的元素也是堆頂元素
        if (data.size() == 0) {
            return last;
        } else {
            // 將刪除的元素放入堆頂
            data.set(0, last);
            // 自上向下調整堆
            shiftDown(0);
            // 返回堆頂元素
            return first;
        }
    }
    /**
     * 獲取堆頂元素，但不刪除
     *
     * @return 堆頂元素
     */
    public T getTop() {
        // 如果堆已經(jīng)為空，就拋出異常
        if (data.isEmpty()) {
            throw new RuntimeException("The heap is empty.");
        }
        return data.get(0);
    }
    /**
     * 獲取堆的大小
     *
     * @return 堆的大小
     */
    public int size() {
        return data.size();
    }
    /**
     * 判斷堆是否為空
     *
     * @return 堆是否為空
     */
    public boolean isEmpty() {
        return data.isEmpty();
    }
    /**
     * 清空堆
     */
    public void clear() {
        data.clear();
    }
    /**
     * 獲取堆中所有的數(shù)據(jù)
     *
     * @return 堆中所在的數(shù)據(jù)
     */
    public List<T> getData() {
        return data;
    }
}

升序比較器

/**
 * 升序比較器
 */
private static class IncComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 - o2;
    }
}

降序比較器

/**
 * 降序比較器
 */
private static class DescComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}

代碼實現(xiàn)

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class Test64 {
    private static class Heap<T> {
        // 堆中元素存放的集合
        private List<T> data;
        // 比較器
        private Comparator<T> cmp;
        /**
         * 構造函數(shù)
         *
         * @param cmp 比較器對象
         */
        public Heap(Comparator<T> cmp) {
            this.cmp = cmp;
            this.data = new ArrayList<>(64);
        }
        /**
         * 向上調整堆
         *
         * @param idx 被上移元素的起始位置
         */
        public void shiftUp(int idx) {
            // 檢查是位置是否正確
            if (idx < 0 || idx >= data.size()) {
                throw new IllegalArgumentException(idx + "");
            }
            // 獲取開始調整的元素對象
            T intent = data.get(idx);
            // 如果不是根元素，則需要上移
            while (idx > 0) {
                // 找父元素對象的位置
                int parentIdx = (idx - 1) / 2;
                // 獲取父元素對象
                T parent = data.get(parentIdx);
                //上移的條件，子節(jié)點比父節(jié)點大，此處定義的大是以比較器返回值為準
                if (cmp.compare(intent, parent) > 0) {
                    // 將父節(jié)點向下放
                    data.set(idx, parent);
                    idx = parentIdx;
                    // 記錄父節(jié)點下放的位置
                }
                // 子節(jié)點不比父節(jié)點大，說明父子路徑已經(jīng)按從大到小排好順序了，不需要調整了
                else {
                    break;
                }
            }
            // index此時記錄是的最后一個被下放的父節(jié)點的位置（也可能是自身），
            // 所以將最開始的調整的元素值放入index位置即可
            data.set(idx, intent);
        }
        /**
         * 向下調整堆
         *
         * @param idx 被下移的元素的起始位置
         */
        public void shiftDown(int idx) {
            // 檢查是位置是否正確
            if (idx < 0 || idx >= data.size()) {
                throw new IllegalArgumentException(idx + "");
            }
            // 獲取開始調整的元素對象
            T intent = data.get(idx);
            // 獲取開始調整的元素對象的左子結點的元素位置
            int leftIdx = idx * 2 + 1;
            // 如果有左子結點
            while (leftIdx < data.size()) {
                // 取左子結點的元素對象，并且假定其為兩個子結點中最大的
                T maxChild = data.get(leftIdx);
                // 兩個子節(jié)點中最大節(jié)點元素的位置，假定開始時為左子結點的位置
                int maxIdx = leftIdx;
                // 獲取右子結點的位置
                int rightIdx = leftIdx + 1;
                // 如果有右子結點
                if (rightIdx < data.size()) {
                    T rightChild = data.get(rightIdx);
                    // 找出兩個子節(jié)點中的最大子結點
                    if (cmp.compare(rightChild, maxChild) > 0) {
                        maxChild = rightChild;
                        maxIdx = rightIdx;
                    }
                }
                // 如果最大子節(jié)點比父節(jié)點大，則需要向下調整
                if (cmp.compare(maxChild, intent) > 0) {
                    // 將較大的子節(jié)點向上移
                    data.set(idx, maxChild);
                    // 記錄上移節(jié)點的位置
                    idx = maxIdx;
                    // 找到上移節(jié)點的左子節(jié)點的位置
                    leftIdx = 2 * idx + 1;
                }
                // 最大子節(jié)點不比父節(jié)點大，說明父子路徑已經(jīng)按從大到小排好順序了，不需要調整了
                else {
                    break;
                }
            }
            // index此時記錄是的最后一個被上移的子節(jié)點的位置（也可能是自身），
            // 所以將最開始的調整的元素值放入index位置即可
            data.set(idx, intent);
        }
        /**
         * 添加一個元素
         *
         * @param item 添加的元素
         */
        public void add(T item) {
            // 將元素添加到最后
            data.add(item);
            // 上移，以完成重構
            shiftUp(data.size() - 1);
        }
        /**
         * 刪除堆頂結點
         *
         * @return 堆頂結點
         */
        public T deleteTop() {
            // 如果堆已經(jīng)為空，就拋出異常
            if (data.isEmpty()) {
                throw new RuntimeException("The heap is empty.");
            }
            // 獲取堆頂元素
            T first = data.get(0);
            // 刪除最后一個元素
            T last = data.remove(data.size() - 1);
            // 刪除元素后，如果堆為空的情況，說明刪除的元素也是堆頂元素
            if (data.size() == 0) {
                return last;
            } else {
                // 將刪除的元素放入堆頂
                data.set(0, last);
                // 自上向下調整堆
                shiftDown(0);
                // 返回堆頂元素
                return first;
            }
        }
        /**
         * 獲取堆頂元素，但不刪除
         *
         * @return 堆頂元素
         */
        public T getTop() {
            // 如果堆已經(jīng)為空，就拋出異常
            if (data.isEmpty()) {
                throw new RuntimeException("The heap is empty.");
            }
            return data.get(0);
        }
        /**
         * 獲取堆的大小
         *
         * @return 堆的大小
         */
        public int size() {
            return data.size();
        }
        /**
         * 判斷堆是否為空
         *
         * @return 堆是否為空
         */
        public boolean isEmpty() {
            return data.isEmpty();
        }
        /**
         * 清空堆
         */
        public void clear() {
            data.clear();
        }
        /**
         * 獲取堆中所有的數(shù)據(jù)
         *
         * @return 堆中所在的數(shù)據(jù)
         */
        public List<T> getData() {
            return data;
        }
    }
    /**
     * 升序比較器
     */
    private static class IncComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    }
    /**
     * 降序比較器
     */
    private static class DescComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }
    private static class DynamicArray {
        private Heap<Integer> max;
        private Heap<Integer> min;
        public DynamicArray() {
            max = new Heap<>(new IncComparator());
            min = new Heap<>(new DescComparator());
        }
        /**
         * 插入數(shù)據(jù)
         *
         * @param num 待插入的數(shù)據(jù)
         */
        public void insert(Integer num) {
            // 已經(jīng)有偶數(shù)個數(shù)據(jù)了（可能沒有數(shù)據(jù)）
            // 數(shù)據(jù)總數(shù)是偶數(shù)個時把新數(shù)據(jù)插入到小堆中
            if ((min.size() + max.size()) % 2 == 0) {
                // 大堆中有數(shù)據(jù)，并且插入的元素比大堆中的元素小
                if (max.size() > 0 && num < max.getTop()) {
                    // 將num加入的大堆中去
                    max.add(num);
                    // 刪除堆頂元素，大堆中的最大元素
                    num = max.deleteTop();
                }
                // num插入到小堆中，當num小于大堆中的最大值進，
                // num就會變成大堆中的最大值，見上面的if操作
                // 如果num不小于大堆中的最大值，num就是自身
                min.add(num);
            }
            // 數(shù)據(jù)總數(shù)是奇數(shù)個時把新數(shù)據(jù)插入到大堆中
            else {
                // 小堆中有數(shù)據(jù)，并且插入的元素比小堆中的元素大
                if (min.size() > 0 && num > min.size()) {
                    // 將num加入的小堆中去
                    min.add(num);
                    // 刪除堆頂元素，小堆中的最小元素
                    num = min.deleteTop();
                }
                // num插入到大堆中，當num大于小堆中的最小值進，
                // num就會變成小堆中的最小值，見上面的if操作
                // 如果num不大于大堆中的最小值，num就是自身
                max.add(num);
            }
        }
        public double getMedian() {
            int size = max.size() + min.size();
            if (size == 0) {
                throw new RuntimeException("No numbers are available");
            }
            if ((size & 1) == 1) {
                return min.getTop();
            } else {
                return (max.getTop() + min.getTop()) / 2.0;
            }
        }
    }
    public static void main(String[] args) {
        DynamicArray array = new DynamicArray();
        array.insert(5);
        System.out.println(array.getMedian()); // 5
        array.insert(2);
        System.out.println(array.getMedian()); // 3.5
        array.insert(3);
        System.out.println(array.getMedian()); // 3
        array.insert(4);
        System.out.println(array.getMedian()); // 3.5
        array.insert(1);
        System.out.println(array.getMedian()); // 3
        array.insert(6);
        System.out.println(array.getMedian()); // 3.5
        array.insert(7);
        System.out.println(array.getMedian()); // 4
        array.insert(0);
        System.out.println(array.getMedian()); // 3.5
        array.insert(8);
        System.out.println(array.getMedian()); // 4
    }
}

運行結果

http://wiki.jikexueyuan.com/project/for-offer/images/82.png" alt="" />