Java:无序数组的中位数（最小堆）

小咪咪 2023-07-12 09:20 13阅读 0赞

中位数，就是数组排序后处于数组最中间的那个元素。如果数组长度是奇数，最中间就是位置为（n+1）／2的那个元素。如果是偶数，中位数是位置为n/2和位置为n/2+1的两个元素的和除以2的结果。

算法要求：**输入一个整数数组，求出本数组的中位数。**

思路1：将数组排序，然后直接从排序数组中找出中位数。时间复杂度取决于排序算法，最快是快速排序，O(nlogn)，或者是非比较的基数排序，时间为O(n),空间为O(n)。

思路2：采用快速排序的分治partition过程。任意挑一个元素，以该元素为支点，将数组分成两部分，左边是小于等于支点的，右边是大于支点的。如果左侧长度正好是(n－1)／2，那么支点恰为中位数。如果左侧长度<(n-1)/2, 那么中位数在右侧，反之，中位数在左侧。 进入相应的一侧继续寻找中位数。

思路3：将数组的前（n+1）／2个元素建立一个最小堆。然后，对于下一个元素，和堆顶的元素比较，如果小于等于，丢弃之，如果大于，则用该元素取代堆顶，再调整堆，接着看下一个元素。重复这个步骤，直到数组为空。当数组都遍历完了，堆顶的元素即是中位数。

**在Java中，PriorityQueue是一个基于优先级堆的无界优先级队列，默认是一个最小堆。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMjQyOTg3_size_16_color_FFFFFF_t_70]  
实现如下：

import java.util.PriorityQueue;
    
    public class Median { 
        public static double median(int[] array) { 
            int heapSize = array.length / 2 + 1;
            PriorityQueue<Integer> heap = new PriorityQueue<>(heapSize);
            for (int i = 0; i < heapSize; i++) { 
                heap.add(array[i]);
            }
            for (int i = heapSize; i < array.length; i++) { 
                if (heap.peek() < array[i]) { 
                    heap.poll();
                    heap.add(array[i]);
                }
            }
            if (array.length % 2 == 1) { 
                return (double) heap.peek();
            } else { 
                return (double) (heap.poll() + heap.peek()) / 2.0;
            }
        }
    
        public static void main(String[] args) { 
            int[] array = new int[]{ 12, 34, 1, 209, 17, 900, -10};
            System.out.println(median(array));
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMjQyOTg3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200308105921176.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMjQyOTg3,size_16,color_FFFFFF,t_70