# 数据流的中位数 1

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

-105 <= num <= 105
在调用 findMedian 之前，数据结构中至少有一个元素
最多 5 * 104 次调用 addNum 和 findMedian

# 题目分析什么是中位数呢

比如说我有一串有序的整数，如果这串整数它的个数为奇数个的话那么中间那个数字就是中位数比如说 arr = [2, 3, 4] 中位数就是 3

如果这串数字它的个数为偶数个的话那就把中间两个数字求一个平均值，比如说 arr = [2, 3] 中位数就是 (2 + 3) / 2 = 2.5 而 2.5 这个平均值就是我们要找的中间值

这是中位数的概念，那数据流中的中位数是指什么呢？

就是这个数据它是不断变化的不是说一开始就把 arr = [2, 3, 4] 这串数字给你固定好了它也是给我们提供了一个 addNum 方法，这个方法来模拟不断去获取新的数据，向这个数据流中添加新的数据那参数就是新来的数据

那我们就是要找到数据流中这多个数字中间的中位数字

# 思路分析

使用大顶堆和小顶堆结合解决问题

我们可以把数据流中的数据分成两部分，一半分是较小的数字，另一半是较大的数字

1 2 3   7 8 9
s s s   s s s

那么我们在较小的部分里面找一个最大的数字，比如说找到的是 3，剩下的数字不用关心是不是有序的

然后较大的数字里面找一个最小的数字，比如说找到的是 7，剩下的数字不用关心是不是有序的

1 2 3   7 8 9
s s 3   7 s s

这样就可以看出一半数据的最大数字，和另一半的最小数字。它俩是不是就是我们的中位数啊

经过上面的描述跟我们之前学的数据结构中的大顶堆和小顶堆比较像

比如前面的一半数据中找最大的数字对应的就是大顶堆，而另一半数据中找最小的数字对应的就是小顶堆

所以接下来我们就可以使用两个堆来实现这道题目

# 下面来看图进行解释一下：

下图中是有一个大堆顶和一个小顶堆，它们之间的堆顶是相对的

其中大顶堆的堆顶元素 3 是最大值，而小顶堆中 3 个元素里 7 是最小值，都处于它们各自的堆顶那么中位数就是 3 和 7 剩余的数字是不需要排序的，反正堆顶元素找到了就能找到它的中位数

但是这是有一个前提：就是我这两个堆的数目个数必须是基本相当的，比如说左边 5 个和右边 1 个那么它们的堆顶元素就不是中位数了。

所以两个堆的数目必须是相等就算是不等最多也不能超过 1 个，比如说左边 4 个右边 3 个这是可以的

这时虽然它们不等但是我们也可以看得出来元素多的那个堆它的堆顶就是中位数或者左边 3 个右边 4 个也是同理

# 总结：

两个堆的元素个数要平衡，最多也不能相差超过 1 个

# 那我们怎么保证两个堆的数据流平衡呢

为了保证两边数据量的平衡

两边个数一样时，左边个数加一
两边个数不一样时，右边个数加一

但是，随便一个数直接加入吗？答：不能

左边个数加一时，应该挑右边最小的加入
右边个数加一时，应该挑左边最大的加入

# 分析一：两边个数一样时，左边个数加一

比如说来了个 4 由于两边个数一样那么将新来的元素左边加

# 分析二：两边个数不一样时，右边个数加一

上面左边是 4 个右边是 3 个它们两边个数不一样那么将新来的元素右边加

那么这样的话就能始终保证两个堆它们的元素个数平衡了，最多相差也不会超过 1 个

但是光有上面的规则还是不够的还是有问题的

比如说现在的情况是两边个数一样

我现在要加一个元素，那么它就会让左边堆的个数加一，那如果我加的元素是 10 呢？

这样显然不行，10 比右边的几个值都大了它肯定不是一个中位数，要让两个堆的各自的堆顶都是中位数才行

# 分析三：左边个数加一时，应该挑右边最小的加入

那怎么办呢？我们的最终目的是希望左边的元素个数变成 4，但是不要直接把它加入到左边，先把新的元素加在右边

加到右边后，我们再从右边取走一个元素，取走它堆里最小的也就是把 7 取走，我们再把取走的 7 加回左边堆里

这样目的就达到了左边是 4 个右边是 3 个

# 分析四：右边个数加一时，应该挑左边最大的加入

将分析三反过来同理的。

# 代码实现：

# 大顶堆和小顶堆的结合类：

	/**
	* 可以扩容的 heap, max 用于指定是大顶堆还是小顶堆
	*/
	public class Heap {
	int[] array;
	int size;
	boolean max;

	public int size() {
	return size;
	}

	public Heap(int capacity, boolean max) {
	this.array = new int[capacity];
	this.max = max;
	}

	/**
	* 获取堆顶元素
	*
	* @return 堆顶元素
	*/
	public int peek() {
	return array[0];
	}

	/**
	* 删除堆顶元素
	*
	* @return 堆顶元素
	*/
	public int poll() {
	int top = array[0];
	swap(0, size - 1);
	size--;
	down(0);
	return top;
	}

	/**
	* 删除指定索引处元素
	*
	* @param index 索引
	* @return 被删除元素
	*/
	public int poll(int index) {
	int deleted = array[index];
	up(Integer.MAX_VALUE, index);
	poll();
	return deleted;
	}

	/**
	* 替换堆顶元素
	*
	* @param replaced 新元素
	*/
	public void replace(int replaced) {
	array[0] = replaced;
	down(0);
	}

	/**
	* 堆的尾部添加元素
	*
	* @param offered 新元素
	*/
	public void offer(int offered) {
	if (size == array.length) {
	// 扩容
	grow();
	}
	up(offered, size);
	size++;
	}

	private void grow() {
	int capacity = size + (size >> 1);
	int[] newArray = new int[capacity];
	System.arraycopy(array, 0,
	newArray, 0, size);
	array = newArray;
	}

	// 将 offered 元素上浮：直至 offered 小于父元素或到堆顶
	private void up(int offered, int index) {
	int child = index;
	while (child > 0) {
	int parent = (child - 1) / 2;
	boolean cmp = max ? offered > array[parent] : offered < array[parent];
	if (cmp) {
	array[child] = array[parent];
	} else {
	break;
	}
	child = parent;
	}
	array[child] = offered;
	}

	public Heap(int[] array, boolean max) {
	this.array = array;
	this.size = array.length;
	this.max = max;
	heapify();
	}

	// 建堆
	private void heapify() {
	// 如何找到最后这个非叶子节点 size / 2 - 1
	for (int i = size / 2 - 1; i >= 0; i--) {
	down(i);
	}
	}

	// 将 parent 索引处的元素下潜：与两个孩子较大者交换，直至没孩子或孩子没它大
	private void down(int parent) {
	int left = parent * 2 + 1;
	int right = left + 1;
	int maxOrMin = parent;
	if (left < size && (max ? array[left] > array[maxOrMin] : array[left] < array[maxOrMin])) {
	maxOrMin = left;
	}
	if (right < size && (max ? array[right] > array[maxOrMin] : array[right] < array[maxOrMin])) {
	maxOrMin = right;
	}
	if (maxOrMin != parent) { // 找到了更大的孩子
	swap(maxOrMin, parent);
	down(maxOrMin);
	}
	}

	// 交换两个索引处的元素
	private void swap(int i, int j) {
	int t = array[i];
	array[i] = array[j];
	array[j] = t;
	}

	/*
	100
	/ \
	10 99
	/ \ / \
	5 6 98 97
	/\ /\ /
	1 2 3 4 96

	100
	/ \
	96 99
	/ \ / \
	10 6 98 97
	/\ /\
	1 2 3 4
	*/
	public static void main(String[] args) {
	Heap heap = new Heap(5, true); //100,10,99,5,6,98,97,1,2,3,4,96
	heap.offer(100);
	heap.offer(10);
	heap.offer(99);
	heap.offer(5);
	heap.offer(6);
	heap.offer(98);
	heap.offer(97);
	heap.offer(1);
	heap.offer(2);
	heap.offer(3);
	heap.offer(4);
	heap.offer(96);
	System.out.println(Arrays.toString(heap.array));
	System.out.println(heap.size);
	System.out.println(heap.poll(3));
	System.out.println(Arrays.toString(heap.array));
	System.out.println(heap.size);
	}
	}

# 解决题目要求的代码：

	/**
	* @author Dkx
	* @version 1.0
	* @2024/1/2222:33
	* @function
	* @comment
	* 数据流的中位数
	*/
	public class E04Leetcode295
	{
	/**
	* 为了保证两边数据量的平衡
	* - 两边个数一样时，左边个数加一
	* - 两边个数不一样时，右边个数加一
	* 但是，随便一个数能直接加入吗？答：不能
	* - 左边个数加一时，把新元素加在右边，弹出右边最小的加入左边
	* - 右边个数加一时，把新元素加在左边，弹出左边最小的加入右边
	*/
	public void addNum(int num)
	{
	// 左边元素个数加一的规则
	// 判断两边堆的元素个数是否相等
	if(left./getSize/size() == right./getSize/size())
	{
	// 先将要添加的值添加到右边堆里
	right.offer(num);
	// 再将右边堆里取一个较小的值添加到左边堆里
	left.offer(right.poll());
	// 右边元素个数加一的规则
	}else
	{
	// 先将要添加的值添加到左边堆里
	left.offer(num);
	// 再将左边堆里取一个较大的值添加到右边堆里
	right.offer(left.poll());
	}
	}

	// 创建左边这半堆
	private Heap left = new Heap(10, true);
	// 创建右边这半堆
	private Heap right = new Heap(10, false);

	// 计算中位数
	public double findMedian()
	{
	// 判断如何左右两边堆的个数相等那么就返回两个数相加除以 2 等于平均值 (中位数)
	if (left.size() == right.size()) {
	return (left.peek() + right.peek()) / 2.0;
	// 如果个数不相等那么左边肯定比右边多了一个那么左边的堆顶元素就是中位数
	} else {
	return left.peek();
	}
	}

	@Override
	public String toString()
	{
	int size = left.size;
	int[] left = new int[size];
	for (int i = 0; i < left.length; i++) {
	left[size - 1 - i] = this.left.array[i];
	}
	int[] right = Arrays.copyOf(this.right.array, this.right.size);
	return Arrays.toString(left) + " <-> " + Arrays.toString(right);
	}

	public static void main(String[] args)
	{
	E04Leetcode295 test = new E04Leetcode295();
	test.addNum(1);
	test.addNum(2);
	test.addNum(3);
	test.addNum(7);
	test.addNum(8);
	test.addNum(9);
	System.out.println(test);
	System.out.println(test.findMedian());
	test.addNum(10);
	System.out.println(test);
	System.out.println(test.findMedian());
	test.addNum(4);
	System.out.println(test);
	System.out.println(test.findMedian());
	}
	}

打印结果：

[2, 1, 3] <-> [7, 8, 9]
5.0
[1, 2, 3, 7] <-> [8, 10, 9]
7.0
[1, 2, 3, 4] <-> [7, 8, 9, 10]
5.5

编程题堆小顶堆大顶堆