6. Find Median from Data Stream

«Истинный баланс достигается не тогда, когда всё замерло, а когда две противоположные силы уравновешивают друг друга в непрерывном движении».
— Дональд Эрвин Кнут

Баланс двух сил: Динамический поиск медианы

В предыдущих задачах мы задействовали одиночные кучи для извлечения экстремумов. Однако в статистике и мониторинге (расчет 50-го перцентиля задержек p50 Latency в потоке метрик) требуется непрерывно удерживать фокус в центре упорядоченных данных.

Задача Find Median from Data Stream (LeetCode №295) — фундаментальный образец архитектурного проектирования потоковых структур.

Условие: Реализовать структуру MedianFinder:

1. AddNum(num int) — добавление нового числа из потока.
2. FindMedian() float64 — возвращение медианы всех накопленных чисел за $O(1)$.

Архитектурный паттерн: Two Heaps (Две кучи)

Чтобы не сортировать массив за $O(N \log N)$ на каждом шаге, мы делим числовой поток на две половины:

1. Левая половина (Small): хранит меньшую половину чисел. Нам требуется за $O(1)$ получать наибольшее из них. Для этого используется Max-Heap.
2. Правая половина (Large): хранит большую половину чисел. Нам требуется за $O(1)$ получать наименьшее из них. Для этого используется Min-Heap.

flowchart LR
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef accent  fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc

    subgraph LeftHalf["Левая половина (Max-Heap)"]
        L["Корень = Max(Small)<br>Размер: k или k + 1"]:::accent
    end

    subgraph Median["Медиана"]
        M["Корень(Left) либо<br>(Корень(Left) + Корень(Right)) / 2"]:::success
    end

    subgraph RightHalf["Правая половина (Min-Heap)"]
        R["Корень = Min(Large)<br>Размер: k"]:::process
    end

    L --- M --- R
  

Инварианты балансировки:

1. Любой элемент в Max-Heap $\le$ любого элемента в Min-Heap.
2. Длины куч различаются не более чем на $1$ элемент: small.Len() >= large.Len().

При вызове AddNum(num):

1. Добавляем num в small (Max-Heap).
2. Выталкиваем вершину из small и переносим в large (Min-Heap) — это гарантирует инвариант упорядоченности.
3. Если large стал больше small, возвращаем наименьший элемент из large обратно в small.

Идиоматичная реализация на Go

package main

import "container/heap"

// Универсальная куча с переключателем Min/Max
type IntHeap struct {
    arr   []int
    isMax bool
}

func (h IntHeap) Len() int           { return len(h.arr) }
func (h IntHeap) Swap(i, j int)      { h.arr[i], h.arr[j] = h.arr[j], h.arr[i] }
func (h IntHeap) Less(i, j int) bool {
    if h.isMax {
        return h.arr[i] > h.arr[j] // Max-Heap
    }
    return h.arr[i] < h.arr[j] // Min-Heap
}

func (h *IntHeap) Push(x any) {
    h.arr = append(h.arr, x.(int))
}

func (h *IntHeap) Pop() any {
    old := h.arr
    n := len(old)
    x := old[n-1]
    h.arr = old[0 : n-1]
    return x
}

type MedianFinder struct {
    small *IntHeap // Max-Heap для нижней половины
    large *IntHeap // Min-Heap для верхней половины
}

func Constructor() MedianFinder {
    s := &IntHeap{isMax: true}
    l := &IntHeap{isMax: false}
    heap.Init(s)
    heap.Init(l)
    return MedianFinder{small: s, large: l}
}

func (this *MedianFinder) AddNum(num int) {
    // 1. Помещаем в Max-Heap
    heap.Push(this.small, num)

    // 2. Балансировка: наибольший из малых уходит в правые
    heap.Push(this.large, heap.Pop(this.small))

    // 3. Поддержание инварианта размера: small.Len() >= large.Len()
    if this.large.Len() > this.small.Len() {
        heap.Push(this.small, heap.Pop(this.large))
    }
}

func (this *MedianFinder) FindMedian() float64 {
    if this.small.Len() > this.large.Len() {
        return float64(this.small.arr[0])
    }
    return float64(this.small.arr[0]+this.large.arr[0]) / 2.0
}

Асимптотический анализ

• AddNum: $O(\log N)$ — фиксированное количество операций Push/Pop.
• FindMedian: $O(1)$ — прямое чтение вершин срезов small.arr[0] и large.arr[0].
• Память: $O(N)$ для хранения потока чисел.

Далее мы применим приоритетные очереди к моделированию процессорного времени: 7. Task Scheduler.