Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Heap & Top K

Guide 3 of 6 · Path 3 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardheap-top-k

Find Median from Data Stream

Problem (restated)

Support addNum(num) and findMedian() over a growing stream. Median is middle (odd) or average of two middles (even).

Intuition

Keep lower half in a max-heap, upper half in a min-heap. Balance sizes so lo has n/2 or n/2+1 elements.

Approaches

Two heaps (max + min)

Tested only
Time O(log n) add, O(1) medianSpace O(n)

Idea. Push into lo or hi by value; rebalance so lo.Count ≥ hi.Count and |lo-hi| ≤ 1. Median from peeks.

Walkthrough. add 1,2,3 → lo=[2,1] hi=[3] → median 2; add 4 → average of 2 and 3 = 2.5.

Trade-offs. Sorted list is O(n) insert; dual heap is the interview target.

Solution
export class MedianFinder {
  private lo: number[] = []; // max-heap (negated via sort desc)
  private hi: number[] = []; // min-heap

  addNum(num: number): void {
    if (this.lo.length === 0 || num <= this.lo[0]!) {
      this.lo.push(num);
      this.lo.sort((a, b) => b - a);
    } else {
      this.hi.push(num);
      this.hi.sort((a, b) => a - b);
    }
    if (this.lo.length > this.hi.length + 1) {
      this.hi.push(this.lo.shift()!);
      this.hi.sort((a, b) => a - b);
    } else if (this.hi.length > this.lo.length) {
      this.lo.push(this.hi.shift()!);
      this.lo.sort((a, b) => b - a);
    }
  }

  findMedian(): number {
    if (this.lo.length > this.hi.length) return this.lo[0]!;
    return (this.lo[0]! + this.hi[0]!) / 2;
  }
}

export class MedianFinder {
  private lo: number[] = []; // max-heap (negated via sort desc)
  private hi: number[] = []; // min-heap

  addNum(num: number): void {
    if (this.lo.length === 0 || num <= this.lo[0]!) {
      this.lo.push(num);
      this.lo.sort((a, b) => b - a);
    } else {
      this.hi.push(num);
      this.hi.sort((a, b) => a - b);
    }
    if (this.lo.length > this.hi.length + 1) {
      this.hi.push(this.lo.shift()!);
      this.hi.sort((a, b) => a - b);
    } else if (this.hi.length > this.lo.length) {
      this.lo.push(this.hi.shift()!);
      this.lo.sort((a, b) => b - a);
    }
  }

  findMedian(): number {
    if (this.lo.length > this.hi.length) return this.lo[0]!;
    return (this.lo[0]! + this.hi[0]!) / 2;
  }
}

Template connection

Heap top-k / order statistics with two priority queues.

Deep dive

Two heaps keep the lower half (max-heap) and upper half (min-heap) balanced by size. Invariant: every value in lower ≤ every value in upper, and sizes differ by at most 1. Median is the max of lower (odd count) or average of the two roots (even). Rebalance after each insert. This is online: you never re-sort the whole stream.

Sorted list baseline

Tested only
Time O(n) per insertSpace O(n)

Idea. Keep numbers sorted; binary-search insert; median at middle.

Trade-offs. Simple and correct; two-heap version is O(log n) insert for interviews.

Solution
/** Naive median: keep a sorted array (O(n) insert). */
export class MedianFinderSorted {
  private a: number[] = [];
  addNum(num: number): void {
    let lo = 0, hi = this.a.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.a[mid]! < num) lo = mid + 1;
      else hi = mid;
    }
    this.a.splice(lo, 0, num);
  }
  findMedian(): number {
    const n = this.a.length;
    const m = n >> 1;
    return n % 2 ? this.a[m]! : (this.a[m - 1]! + this.a[m]!) / 2;
  }
}

/** Naive median: keep a sorted array (O(n) insert). */
export class MedianFinderSorted {
  private a: number[] = [];
  addNum(num: number): void {
    let lo = 0, hi = this.a.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.a[mid]! < num) lo = mid + 1;
      else hi = mid;
    }
    this.a.splice(lo, 0, num);
  }
  findMedian(): number {
    const n = this.a.length;
    const m = n >> 1;
    return n % 2 ? this.a[m]! : (this.a[m - 1]! + this.a[m]!) / 2;
  }
}

Reflection