Алгоритми та структури даних · Senior · Запитання 56 з 75
Як ефективно підтримувати поточну медіану потоку?
- 1Вставляти у відсортований масив і читати середину
- 2Тримати поточне середнє, яке дорівнює медіані
- ✓Правильна відповідь: Max-купа для нижньої половини, min-купа для верхньої
Пояснення
Тримайте купи збалансованими за розміром; медіана - один із коренів або їхнє середнє. Кожна вставка O(log n). Відсортований масив потребує O(n) зсувів на вставку, а середнє - не медіана.