Algorytmy i struktury danych · Senior · Pytanie 56 z 75
Jak wydajnie utrzymywać bieżącą medianę strumienia?
- 1Wstawiać do posortowanej tablicy i czytać środek
- 2Trzymać bieżącą średnią, która równa się medianie
- ✓Poprawna odpowiedź: Max-kopiec dla dolnej połowy, min-kopiec dla górnej
Wyjaśnienie
Trzymaj kopce zbalansowane rozmiarem; mediana to jeden z korzeni lub ich średnia. Każde wstawienie to O(log n). Posortowana tablica wymaga O(n) przesunięć na wstawienie, a średnia to nie mediana.