堆--求中位数

作者: 暮想sun | 来源:发表于2020-01-09 00:02 被阅读0次

    针对动态数据,求排序后处于中间的数据
    思路:维护两个堆,一个大顶堆,一个小顶堆。大顶堆中存储前半部分数据,小顶堆中存储后半部分数据,且小顶堆中的数据都大于大顶堆中的数据。如果有 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;
        }
    
    
    

    相关文章

      网友评论

        本文标题:堆--求中位数

        本文链接:https://www.haomeiwen.com/subject/qrseactx.html