堆--求中位数

针对动态数据，求排序后处于中间的数据
思路：维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。如果有 n 个数据，n 是偶数，从小到大排序，那前 n/2​ 个数据存储在大顶堆中，后 n/2个数据存储在小顶堆中。这样，大顶堆中的堆顶元素就是我们要找的中位数。如果 n 是奇数，情况是类似的，大顶堆就存储 n/2​+1 个数据，小顶堆中就存储 n/2​ 个数据。

//数据数组
    private int[] data = new int[10];

    //数据大小
    private int size;

    //大顶堆数据数组
    private int[] bigHeap = new int[5];

    //大顶堆数据大小
    private int bigHeapSize;

    //小顶堆数据数组
    private int[] smallHeap = new int[5];

    //小顶堆数据大小
    private int smallHeapSize;

    //添加数据,暂不考虑扩容，固定数组大小。添加数据不会超标.
    public void add(int value) {
        data[size++] = value;

        //偶数情况下，大顶堆n/2，小顶堆n/2，奇数情况下，大顶堆n/2+1,小顶堆n/2.且大顶堆的数据比小顶堆多
        if (size % 2 == 0) {
            //大顶堆堆顶元素大于该元素，将大顶堆元素删除。放入小顶堆。该元素加入大顶堆。
            int temp = value;
            if (bigHeap[0] > value) {
                temp = bigHeap[0];
                bigHeap[0] = value;
                bigHeapAdjust(bigHeap, 0, bigHeapSize);
            }
            smallHeap[smallHeapSize++] = temp;
            smallHeapAdjust(smallHeap,0, smallHeapSize);
        } else {
            //和小顶堆堆顶元素大小判断
            int temp = value;
            if (smallHeapSize != 0 && smallHeap[0] < value) {
                temp = smallHeap[0];
                smallHeap[0] = value;
                smallHeapAdjust(smallHeap, 0, smallHeapSize);
            }

            bigHeap[bigHeapSize++] = temp;
            bigHeapAdjust(bigHeap,0, bigHeapSize);
        }

    }

    public int medianNum() {
        return bigHeap[0];
    }

    public static void smallHeapAdjust(int[] data, int index, int length) {
        int temp = data[0];
        for (int i = index * 2 + 1; i < length; i = i * 2 + 1) {
            if (i + 1 < length && data[i] > data[i + 1]) {
                //左孩子节点大于右孩子节点，指向右孩子
                i++;
            }

            //如果该结点比最小的孩子节点小，退出
            if (temp < data[i]) {
                break;
            }

            //将最小的孩子结点的值赋值给该结点
            data[index] = data[i];
            index = i;
        }

        data[index] = temp;
    }

    public static void bigHeapAdjust(int[] data, int index, int length) {

        //从该结点的左子结点开始，也就是2i+1处开始
        int temp = data[index];
        for (int i = index * 2 + 1; i < length; i = i * 2 + 1) {

            if (i + 1 < length && data[i] < data[i + 1]) {
                //左孩子节点小于右孩子节点，指向右孩子
                i++;
            }

            //如果该结点比最大的孩子节点大，退出
            if (temp >= data[i]) {
                break;
            }

            //将最大的孩子结点的值赋值给该结点
            data[index] = data[i];
            index = i;
        }

        data[index] = temp;
    }