Find Median from Data Stream — duy trì trung vị khi số liệu chảy vào liên tục bằng kỹ thuật hai heap?

Ý tưởng: Chia dữ liệu thành 2 nửa cân bằng:
- Max-heap low giữ nửa nhỏ (đỉnh = lớn nhất nửa nhỏ).
- Min-heap high giữ nửa lớn (đỉnh = nhỏ nhất nửa lớn).

Giữ kích thước hai heap chênh nhau ≤ 1. Trung vị = đỉnh heap lớn hơn (số lẻ) hoặc trung bình hai đỉnh (số chẵn).

Hình dung: một cái cân thăng bằng — thêm số vào, nếu lệch thì chuyển đỉnh từ bên nặng sang bên nhẹ.

// minh hoạ logic; thực tế dùng binary heap thay cho sort
class MedianFinder {
  private low: number[] = []  // max-heap (nửa nhỏ)
  private high: number[] = [] // min-heap (nửa lớn)
  addNum(num: number): void {
    this.low.push(num); this.low.sort((a, b) => b - a)
    this.high.push(this.low.shift()!); this.high.sort((a, b) => a - b)
    if (this.high.length > this.low.length) this.low.push(this.high.shift()!), this.low.sort((a, b) => b - a)
  }
  findMedian(): number {
    if (this.low.length > this.high.length) return this.low[0]
    return (this.low[0] + this.high[0]) / 2
  }
}

Độ phức tạp: addNum O(log n) với binary heap thật, findMedian O(1); bộ nhớ O(n).

Lưu ý: Mấu chốt là rebalance sau mỗi lần thêm — đẩy qua heap kia rồi kéo lại để cả phần tử lẫn kích thước đều đúng vị trí.

Idea: Split data into 2 balanced halves:
- Max-heap low holds the smaller half (top = largest of small half).
- Min-heap high holds the larger half (top = smallest of large half).

Keep their sizes within 1 of each other. The median is the top of the larger heap (odd count) or the average of both tops (even count).

Picture it: a balance scale — add a number, and if it tilts, move the top from the heavier side to the lighter.

// illustrative logic; real code uses a binary heap instead of sort
class MedianFinder {
  private low: number[] = []  // max-heap (small half)
  private high: number[] = [] // min-heap (large half)
  addNum(num: number): void {
    this.low.push(num); this.low.sort((a, b) => b - a)
    this.high.push(this.low.shift()!); this.high.sort((a, b) => a - b)
    if (this.high.length > this.low.length) this.low.push(this.high.shift()!), this.low.sort((a, b) => b - a)
  }
  findMedian(): number {
    if (this.low.length > this.high.length) return this.low[0]
    return (this.low[0] + this.high[0]) / 2
  }
}

Complexity: addNum O(log n) with a real binary heap, findMedian O(1); space O(n).

Note: The key is rebalancing after each insert — push through the other heap then pull back so both value and size land correctly.