数据流的中位数 · 交互式算法学习

1class Heap {2  constructor(compare) {3    this.a = [];4    this.compare = compare5  }6  push(x) {7    const a = this.a;8    a.push(x);9    let i = a.length - 1;10    while (i) {11      const p = (i - 1) >> 1;12      if (!this.compare(a[i], a[p])) break;13      [a[i], a[p]] = [a[p], a[i]];14      i = p15    }16  }17  pop() {18    const a = this.a;19    if (!a.length) return undefined;20    const top = a[0],21      last = a.pop();22    if (a.length) {23      a[0] = last;24      for (let i = 0;;) {25        let best = i,26          l = i * 2 + 1,27          r = l + 1;28        if (l < a.length && this.compare(a[l], a[best])) best = l;29        if (r < a.length && this.compare(a[r], a[best])) best = r;30        if (best === i) break;31        [a[i], a[best]] = [a[best], a[i]];32        i = best33      }34    }35    return top36  }37  peek() {38    return this.a[0]39  }40  get size() {41    return this.a.length42  }43}44class MedianFinder {45  constructor() {46    this.lo = new Heap((a, b) => a > b);47    this.hi = new Heap((a, b) => a < b)48  }49  addNum(x) {50    this.lo.push(x);51    this.hi.push(this.lo.pop());52    if (this.hi.size > this.lo.size) this.lo.push(this.hi.pop())53  }54  findMedian() {55    return this.lo.size > this.hi.size ? this.lo.peek() : (this.lo.peek() + this.hi.peek()) / 256  }57}