解题思路：

在数据流中，数据会不断涌入结构中，那么也就面临着需要多次动态调整以获得中位数。 因此实现的数据结构需要既需要快速找到中位数，也需要做到快速调整。

首先能想到就是 二叉搜索树，在平衡状态下，树顶必定是中间数，然后再根据长度的奇偶性决定是否取两个数。

此方法效率高，但是手动编写较费时费力。

根据只需获得中间数的想法，可以将数据分为左右两边，一边以最大堆的形式实现，可以快速获得左侧最大数， 另一边则以最小堆的形式实现。其中需要注意的一点就是左右侧数据的长度差不能超过1。 这种实现方式的效率与AVL平衡二叉搜索树的效率相近，但编写更快；

平衡二叉查找树 ：简称平衡二叉树。由前苏联的数学家 A delse- V elskil 和 L andis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。它具有如下几个性质：

查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(log n)；

图解： （ 图解来源-Maple ）

动态维护一个最大堆和最小堆，最大堆存储一半数据，最小堆存储一半数据，维持最大堆的堆顶比最小堆的堆顶小，并且两个堆的大小最多相差1。

插入新元素时，具体情况分析如下：

JS 实现：

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，以上就是本篇分享~ 撰文不易，点赞鼓励👍👍👍
我是掘金安东尼，公众号同名，日拱一卒、日掘一金，再会~
  
分类：
 前端
 
标签：
 
前端JavaScript算法
 
  
 

      安装掘金浏览器插件
     
多内容聚合浏览、多引擎快捷搜索、多工具便捷提效、多模式随心畅享，你想要的，这里都有！
 前往安装
     
 

    掘金安东尼
        VIP.5 如鱼得水
        小干事 @ 伟大复兴
         24,000