演算法

1function medianResort(stream: number[]): number[] {
2  const seen: number[] = [], out: number[] = [];
3  for (const x of stream) {
4    seen.push(x);
5    const s = [...seen].sort((a, b) => a - b);
6    const m = s.length >> 1;
7    out.push(s.length % 2 ? s[m] : (s[m - 1] + s[m]) / 2);
8  }
9  return out;
10}
11 
12function medianSorted(stream: number[]): number[] {
13  const s: number[] = [], out: number[] = [];
14  for (const x of stream) {
15    let lo = 0, hi = s.length;
16    while (lo < hi) {
17      const mid = (lo + hi) >> 1;
18      if (s[mid] <= x) lo = mid + 1; else hi = mid;
19    }
20    s.splice(lo, 0, x); // shifts everything after lo
21    const m = s.length >> 1;
22    out.push(s.length % 2 ? s[m] : (s[m - 1] + s[m]) / 2);
23  }
24  return out;
25}
26 
27class Heap {
28  private a: number[] = [];
29  constructor(private less: (x: number, y: number) => boolean) {}
30  get size(): number { return this.a.length; }
31  peek(): number { return this.a[0]; }
32  push(x: number): void {
33    const a = this.a;
34    a.push(x);
35    for (let i = a.length - 1; i > 0; ) {
36      const p = (i - 1) >> 1;
37      if (!this.less(a[i], a[p])) break;
38      [a[i], a[p]] = [a[p], a[i]];
39      i = p;
40    }
41  }
42  pop(): number {
43    const a = this.a, top = a[0], last = a.pop()!;
44    if (a.length) {
45      a[0] = last;
46      for (let i = 0; ; ) {
47        const l = 2 * i + 1, r = l + 1;
48        let best = i;
49        if (l < a.length && this.less(a[l], a[best])) best = l;
50        if (r < a.length && this.less(a[r], a[best])) best = r;
51        if (best === i) break;
52        [a[i], a[best]] = [a[best], a[i]];
53        i = best;
54      }
55    }
56    return top;
57  }
58}
59 
60function medianHeaps(stream: number[]): number[] {
61  const low = new Heap((a, b) => a > b);  // max-heap: smaller half
62  const high = new Heap((a, b) => a < b); // min-heap: larger half
63  const out: number[] = [];
64  for (const x of stream) {
65    if (low.size === 0 || x <= low.peek()) low.push(x);
66    else high.push(x);
67    if (low.size > high.size + 1) high.push(low.pop());
68    else if (high.size > low.size) low.push(high.pop());
69    out.push(low.size > high.size ? low.peek() : (low.peek() + high.peek()) / 2);
70  }
71  return out;
72}