这是我参与11月更文挑战的第25天，活动详情查看：2021最后一次更文挑战
算法系列， 日拱一卒。 更多精彩，请关注我的 算法专栏 (●'◡'●)
本篇带来利用大小堆解决“获取数据流的中位数”的问题。
题目：
代码语言：javascript复制中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。进阶:
如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？解题思路：
在数据流中，数据会不断涌入结构中，那么也就面临着需要多次动态调整以获得中位数。 因此实现的数据结构需要既需要快速找到中位数，也需要做到快速调整。
首先能想到就是二叉搜索树，在平衡状态下，树顶必定是中间数，然后再根据长度的奇偶性决定是否取两个数。
此方法效率高，但是手动编写较费时费力。
根据只需获得中间数的想法，可以将数据分为左右两边，一边以最大堆的形式实现，可以快速获得左侧最大数， 另一边则以最小堆的形式实现。其中需要注意的一点就是左右侧数据的长度差不能超过1。 这种实现方式的效率与AVL平衡二叉搜索树的效率相近，但编写更快；
- AVL 平衡二叉搜索树
平衡二叉查找树：简称平衡二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。它具有如下几个性质：
- 可以是空树。
- 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。
查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(log n)；
图解：（图解来源-Maple）
动态维护一个最大堆和最小堆，最大堆存储一半数据，最小堆存储一半数据，维持最大堆的堆顶比最小堆的堆顶小，并且两个堆的大小最多相差1。
插入新元素时，具体情况分析如下：
JS 实现：
代码语言：javascript复制const MedianFinder = function () {
// 默认最大堆
const defaultCmp = (x, y) => x > y;
// 交换元素
const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]);
// 堆类，默认最大堆
class Heap {
constructor(cmp = defaultCmp) {
this.container = [];
this.cmp = cmp;
}
// 插入
insert(data) {
const { container, cmp } = this;
container.push(data);
let index = this.size() - 1;
while (index) {
let parent = (index - 1) >> 1;
if (!cmp(container[index], container[parent])) {
return;
}
swap(container, index, parent);
index = parent;
}
}
// 弹出堆顶，并返回
pop() {
const { container, cmp } = this;
if (!this.size()) {
return null;
}
swap(container, 0, this.size() - 1);
const res = container.pop();
const length = this.size();
let index = 0,
exchange = index * 2 1;
while (exchange < length) {
// // 以最大堆的情况来说：如果有右节点，并且右节点的值大于左节点的值
let right = index * 2 2;
if (right < length && cmp(container[right], container[exchange])) {
exchange = right;
}
if (!cmp(container[exchange], container[index])) {
break;
}
swap(container, exchange, index);
index = exchange;
exchange = index * 2 1;
}
return res;
}
// 获取堆大小
size() {
return this.container.length;
}
// 获取堆顶
peek() {
if (this.size()) return this.container[0];
return null;
}
}
// 最大堆
this.A = new Heap();
// 最小堆
this.B = new Heap((x, y) => x < y);
};
MedianFinder.prototype.addNum = function (num) {
if (this.A.size() !== this.B.size()) {
// 当N为奇数，需要向B添加一个元素
// 先将num插入A，再将A堆顶弹出，插入B
this.A.insert(num);
this.B.insert(this.A.pop());
} else {
// 当N为偶数，需要向A添加一个元素
// 先将num插入B，再将B堆顶弹出，插入A
this.B.insert(num);
this.A.insert(this.B.pop());
}
};
MedianFinder.prototype.findMedian = function () {
// 若总和为偶数，返回两个堆顶的平均数
// 若总和为奇数，返回A的堆顶
return this.A.container.length === this.B.container.length
? (this.A.peek() this.B.peek()) / 2
: this.A.peek();
};基于图解再看代码实现，就太清晰了~~
OK，以上就是本篇分享~ 撰文不易，点赞鼓励
