1.概述

本文介绍了如何查找整数流的中位数。

我会通过示例说明问题，分析问题，最后给出几种Java解决方案。

2.问题描述

中位数（又称中值）指一个有序数据集的中间值。对于一组整数，小于中位数的元素与大于中位数的元素一样多。

在一组有序数据集中：

• 如果元素个数为奇数，那么中间那个元素是中位数：在有序整数集合{5，7，10}中，中位数是7；

• 如果元素个数为偶数，没有中间元素，那么中位数为两个中间元素的平均值：在有序整数集合{5，7，8，10}中，中位数为 （7+8）/ 2 = 7.5。

现在，假设输入是数据流而非一个有限集合。可以把整数流的中位数定义为，到目前为止已读取整数集合的中位数。

问题可以形式化描述为：对于给定的整数流输入，设计一个类，为读取的每个整数执行下面两个任务：

1. 将整数添加到整数集

2. 查找目前为止已读取整数集合的中位数
   

例如：

add 5         // sorted-set = { 5 }, size = 1
中位数 -> 5

add 7         // sorted-set = { 5, 7 }, size = 2
中位数 -> (5 + 7) / 2 = 6

add 10        // sorted-set = { 5, 7, 10 }, size = 3
中位数 -> 7

add 8         // sorted-set = { 5, 7, 8, 10 }, size = 4
中位数 -> (7 + 8) / 2 = 7.5
..

尽管输入的整数流是无限的，但我们假设可以把数据流中的所有元素一次存到内存中。

可以将任务用下面的代码表示：

void add(int num);

double getMedian();

3.朴素方法

3.1.有序列表

让我们从一个简单的想法开始：通过照索引访问列表的中间元素或者中间两个元素，计算整数有序列表的中位数。getMedian操作的时间杂度复为O（1）。

添加新的整数时，必须确保其在列表中的位置正确，让列表保持有序。操作在O（n）时间内完成，其中n代表列表长度。因此，向列表添加新元素，同时计算新的中位数时间成本为O（n）。

3.2.改进朴素方法

add操作以线性时间复杂度运行，这不是最优解。让我们尝试在本节中解决这个问题。

可以把列表分为两个有序列表：较小一列整数降序，较大的一列整数升序。我们可以找到合适的数列添加新整数，这样两个列表长度差最大为1：

if 元素比较大一列中的最小值还要小:
    新整数插入较小的一列
    if 元素比较小一列中的最大值还要大:
        移除该列的最大值并插入到较大一列的列首(也称再平衡)
else
    新整数插入较大的一列:
    if 较大一列中的整数远大于较小一列:
        移除该列的最小值并加到较大一列的列尾(再平衡)

现在，我们开始计算中位数：

If 两个列表的长度相等:
    median = (较小的一列的最大值 + 较大一列中的最小值) / 2
else if 较小的一列中的元素更多:
    median = 较小的一列的最大值
else if 较大的一列中的元素更多:
    median = 较大一列中的最小值

尽管只是把add运算的时间复杂度改进为常数，但我们已经取得了进展。

让我们分析访问的列表元素。我们可能会在add操作（排序）移动元素过程中访问元素。更重要的是，再平衡执行add操作与getMedian操作过程中访问了较大数列中的最小值和较小数列中的最大值（极值）。

可以看到极值为各自列表的第一个元素。因此，我们必须优化索引为0的元素访问，缩短add操作的整体运行时间。

4.基于堆的方法

让我们总结朴素方法，进一步了解问题：

1. 必须在O（1）时间内得到数据中的最小元素或最大元素。

2. 只要可以高效地获得最小或最大元素，就不必按排序顺序保留元素。

3. 我们需要找到添加元素时间小于O（n）的方法。

接下来将研究Heap数据结构，它能帮助我们有效地达成目标。

4.1.Heap数据结构

Heap（堆）通常采用数组实现，但可以把它看作二叉树。

Heap对元素的约束：

4.1.1.最大堆特性

（子）节点的值不能大于其父节点的值。因此，在最大堆中，根节点始终具有最大值。

4.1.2.最小堆特性

（父）节点的值不能大于其子节点的值。因此，在最小堆中，根节点始终具有最小值。

在Java中，PriorityQueue表示一个堆。让我们继续，开始进入使用堆的第一种解决方案。

4.2.第一种解决方案

让用堆替换朴素方法中的列表：

• 最小堆保存较大的一半元素，最小值位于根元素

• 最大堆保存较小的一半元素，最大值位于根元素

现在，可以把传入的整数与最小堆根元素进行比较，并加到对应的一半数列中。接下来，如果插入后两个堆大小差距大于1，可以为堆进行重新平衡，让差距最大等于1：

if size(minHeap) > size(maxHeap) + 1:
    移除minHeap根元素,插入maxHeap
if size(maxHeap) > size(minHeap) + 1:
    移除maxHeap根元素,插入minHeap

通过这种方法，如果得到的两个堆大小相等，可以中位数等于两个堆的根元素平均值。否则，元素多的那个堆，其根元素就是中位数。

我们用PriorityQueue表示堆。PriorityQueue默认是最小堆。可以使用Comparator.reverserOrder创建最大堆，排序方式为自然逆序：

class MedianOfIntegerStream {

    private Queue<Integer> minHeap, maxHeap;

    MedianOfIntegerStream() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    }

    void add(int num) {
        if (!minHeap.isEmpty() && num < minHeap.peek()) {
            maxHeap.offer(num);
            if (maxHeap.size() > minHeap.size() + 1) {
                minHeap.offer(maxHeap.poll());
            }
        } else {
            minHeap.offer(num);
            if (minHeap.size() > maxHeap.size() + 1) {
                maxHeap.offer(minHeap.poll());
            }
        }
    }

    double getMedian() {
        int median;
        if (minHeap.size() < maxHeap.size()) {
            median = maxHeap.peek();
        } else if (minHeap.size() > maxHeap.size()) {
            median = minHeap.peek();
        } else {
            median = (minHeap.peek() + maxHeap.peek()) / 2;
        }
        return median;
    }
}

分析代码运行时间之前，让我们看一下堆操作的时间复杂度：

find-min/find-max        O(1)    

delete-min/delete-max    O(log n)

insert                   O(log n)

因此，getMedian操作可以在O（1）时间内执行完成，因为它只用到了find-min和find-max。add操作的时间复杂度为O(log n)：三次insert/delete调用，每次调用花费的时间都需要O(log n)。

4.3.堆大小保持不变

在之前的方法中，我们将每个新元素与堆的根元素进行了比较。让我们尝试堆的另一种用法，可以利用堆本身的特性在合适的一半数据中添加新元素。

与之前的解决方案一样，先两个堆开始：一个最小堆和一个最大堆。接下来，加入一个条件：最大堆的大小必须始终为(n / 2) ，而最小堆的大小要么是(n / 2) 要么等于(n / 2) + 1，视两个堆的元素总和而定。换句话说，当元素总数为奇数时，只能允许最小堆包含一个额外元素。

由于堆大小不变，因此如果两个堆大小都是(n / 2)，那么可以计算中位数等于两个堆的根元素平均值。否则，最小堆的根元素就是中位数。

当添加一个新的整数时，有两种情况：

1.所有元素的个数总和是偶数
   size(min-heap) == size(max-heap) == (n / 2)

2.所有元素的个数总和是奇数
   size(max-heap) == (n / 2)
   size(min-heap) == (n / 2) + 1

可以通过把新元素添加到其中一个堆并每次重新平衡维持不变：

重新平衡的工作原理是把最大元素从最大堆移动到最小堆，或者把最小元素从最小堆移动到最大堆。这样，尽管新的整数添加到堆之前没有进行比较，但随后的重新平衡确保了较大与较小数列的底层平衡。

下面使用JavaPriorityQueues实现：

class MedianOfIntegerStream {

    private Queue<Integer> minHeap, maxHeap;

    MedianOfIntegerStream() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    }

    void add(int num) {
        if (minHeap.size() == maxHeap.size()) {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        } else {
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
    }

    double getMedian() {
        int median;
        if (minHeap.size() > maxHeap.size()) {
            median = minHeap.peek();
        } else {
            median = (minHeap.peek() + maxHeap.peek()) / 2;
        }
        return median;
    }
}

操作的时间复杂度保持不变：getMedian耗费的时间为O（1），而add的运行时间为O（log n），调用次数完全相同。

两种基于堆的解决方案空间和时间复杂度相似。尽管第二种解决方案很聪明并且实现更简洁，但是这种方法并不直观。而第一种解决方案更符合我们的直觉，因此更容易推断其add操作的正确性。

5.总结

在本文中，我们学习了如何计算整数流的中位数。我们评估了几种解决方案，用PriorityQueue给出了两个不同的Java实现。