DATA·II Структуры данных Глава 18 из 65
Кто следующий
Приёмный покой: больные прибывают каждые несколько минут, врачей двое, и решать, кого звать, приходится вам. Сначала живая очередь, потом список, потом куча — дерево, которое живёт в массиве без единой ссылки. По дороге встретятся хирург Наполеона, придумавший сортировку раненых, десять сильнейших землетрясений из потока и календарь событий, по которому живёт сам приёмный покой.
Структуры данных
- 13 Сложность
- 14 Массивы
- 15 Стек и очередь
- 16 Хеш-таблицы
- 17 Деревья
- 18 Кучи вы здесь
- 19 Графы
Опирается на: 17 · Сад деревьев поиска
Что вы унесёте из главы
- держать самое срочное под рукой: очередь с приоритетом на куче и модуль heapq
- как куча живёт в массиве и почему добавление и извлечение стоят O(log n), а построение — O(n)
- находить k лучших в потоке, сливать отсортированные списки и моделировать события по календарю
Прошлая глава кончилась в приёмном покое. Больных привозят одного за другим, у каждого своя беда, и первым лечить надо того, кому хуже всех, когда бы он ни приехал. Дерево поиска из главы 17 с этим справилось бы: оно держит всех по порядку, и самый тяжёлый лежит на краю. Но оно делает лишнюю работу. Диспетчеру не нужен весь порядок — ни второй по тяжести, ни сотый. Ему нужен один ответ на один вопрос, который задают снова и снова, пока в дверь входят новые люди: кто следующий?
В этой главе вы сядете за стойку диспетчера. Сначала решать будете сами, потом передадите решение программе — очереди, списку и, наконец, куче, — а после каждой смены сверите два числа: сколько ждали больные и сколько работал диспетчер.
Рейн, 1792. Сначала — самых тяжёлых
Правило Ларрея — уже алгоритм. У каждого больного есть число, срочность, и брать надо того, у кого она наибольшая. Дальше вопрос только в скорости: как быстро находить такого больного, когда ждущих много и всё время приходят новые.
Стойка диспетчера
Ниже — приёмный покой. Больные входят слева, у каждого на карточке номер категории: 1 — красная, самая срочная, 5 — синяя. Справа два врача. Когда врач освобождается, смена останавливается и ждёт вас: коснитесь того, кого позвать. Под приёмным покоем — счёт: сколько в среднем и сколько дольше всех ждали больные каждого цвета. Сыграйте пару часов, потом переключите диспетчера на программу — «по приходу», «по тяжести» — и сравните на тех же больных.
Если вы звали красных и оранжевых первыми, ваш счёт похож на счёт режима «по тяжести»: срочные ждут минуты, синие — дольше. «По приходу» уравнивает всех: красный ждёт столько же, сколько человек с занозой, и в загруженный день это десятки минут.
Режим «по тяжести» сделать программой легко: держать ждущих в какой-нибудь коллекции и каждый раз доставать из неё самого срочного. Такую коллекцию называют очередью с приоритетом. Как стек и очередь из главы 15, это абстрактный тип: он описан операциями, а не устройством. Операций две — добавить элемент со своим ключом и достать элемент с наименьшим ключом. Договоримся, что «наименьший» значит «самый срочный»: у красной категории номер 1, и в Манчестерской шкале так и считают. Вопрос главы — из чего очередь с приоритетом сделать.
Попытка первая: список
Начнём с обычного списка. Пришёл больной — append, это $O(1)$. Позвали — min находит самого срочного, remove убирает. Ключом пусть будет кортеж (категория, номер прихода): кортежи сравниваются по первому элементу, при равенстве — по второму, как мы видели в главе 6. Среди равных по тяжести первым окажется тот, кто пришёл раньше, — это честно.
В приёмном покое ждут десять-двадцать человек, и там список справится. Но очередь с приоритетом бывает и длиннее: вызовы скорой по всему большому городу, задания на сервере, события в моделировании — сотни тысяч элементов. Засечём, сколько стоит один больной, если ждущих тысяча, десять тысяч и сто тысяч.
Десятки микросекунд на тысяче, больше миллисекунды на ста тысячах: ждущих в десять раз больше — каждый вызов почти в десять раз дороже. Это линейное время из главы 13, и оно понятно: min смотрит на всех, remove снова ищет и потом сдвигает хвост.
А если держать список отсортированным? Тогда самый срочный всегда в начале. Но достать его — pop(0), а мы знаем из главы 14, что это сдвиг всех остальных на ячейку. Перевернём порядок, чтобы срочный стоял в конце, — pop() станет $O(1)$, зато дорогим станет приход: место нового больного двоичным поиском (модуль bisect) найдётся за $O(\log n)$, но вставка в середину сдвигает половину списка. Одна из двух операций всегда линейная.
| Как хранить | Пришёл | Позвали |
|---|---|---|
| список как есть | $O(1)$ | $O(n)$ |
| отсортированный список | $O(n)$ | $O(1)$ |
| дерево поиска (глава 17) | $O(\log n)$ | $O(\log n)$ |
| куча (эта глава) | $O(\log n)$ | $O(\log n)$ |
Сбалансированное дерево поиска даёт обе операции за логарифм. Но оно хранит полный порядок, а за порядок платят: повороты, указатели, по две ссылки на узел. Нельзя ли заплатить меньше, раз весь порядок нам не нужен?
Куча: начальник срочнее подчинённых
Вспомните, как устроена армия или большая контора. У каждого начальника несколько подчинённых, у тех свои. Попросим одного: пусть каждый начальник будет срочнее своих подчинённых. Больше ничего — подчинённые одного начальника между собой не упорядочены, соседние отделы друг другу никто. Из одного этого условия следует, что самый срочный — на самом верху: у любого другого есть начальник срочнее.
Двоичное дерево с таким условием и есть куча: ключ каждого узла не больше ключей его детей. Сравните с деревом поиска из прошлой главы. Там порядок горизонтальный: левые потомки меньше узла, правые больше, и по дереву можно найти что угодно. В куче порядок только вертикальный: по любой дороге от корня вниз ключи не убывают, а слева и справа — что угодно. Найти в куче произвольный элемент так же трудно, как в мешке. Зато наименьший — всегда в корне, и условие такое слабое, что поддерживать его почти ничего не стоит.
По-английски структура называется heap, «куча», а по-русски её ещё называют пирамидой. Совпадение слов с «кучей» — областью памяти, где языки программирования размещают объекты, — случайное: это две разные вещи.
Дерево без указателей
Вторая половина идеи — как кучу хранить. Будем заполнять дерево этажами, сверху вниз и на каждом этаже слева направо, без пропусков. Такое дерево называют полным: все этажи заполнены, кроме, может быть, последнего, а последний заполняется слева без дыр. Пронумеруем узлы в том же порядке, этаж за этажом, начиная с нуля. Корень — 0, его дети — 1 и 2, их дети — 3, 4, 5, 6 и так далее. Попробуйте по рисунку угадать, как связаны номера родителя и детей.
У узла номер $i$ дети имеют номера $2i + 1$ и $2i + 2$, а родитель — $(i - 1) \mathbin{//} 2$. Значит, дереву не нужны ни узлы-объекты, ни ссылки на детей, как в главе 17: хватает обычного списка, а связи вычисляются арифметикой, как адрес ячейки массива в главе 14. Дерево существует только в нашей голове, а в памяти — сплошной ряд ссылок без единой лишней.
И бесплатно получается то, ради чего в прошлой главе понадобились повороты. Полное дерево не может выродиться в палку: оно всегда настолько низкое, насколько возможно. На этажах по 1, 2, 4, 8, … узлов, и если в куче $n$ элементов, этажей $\lfloor \log_2 n \rfloor + 1$. Миллион элементов — двадцать этажей, миллиард — тридцать.
В куче 20 элементов. В какой ячейке родитель элемента из ячейки 12 и есть ли у ячейки 12 дети?
$(12 - 1) \mathbin{//} 2 = 5$. Дети были бы в ячейках $2 \cdot 12 + 1 = 25$ и $26$, но последняя ячейка — 19, значит, 12 — лист. Вообще в куче из $n$ элементов листья — все ячейки начиная с $n \mathbin{//} 2$, то есть половина (при нечётном $n$ — с округлением вверх). Это нам ещё пригодится.
Просеивание
Осталось научиться добавлять и доставать, не ломая условия кучи. Оба раза работает один приём — просеивание: нарушителя меняют местами с соседом по вертикали, пока порядок не восстановится.
Добавить. Новый элемент кладём в первую свободную ячейку — в конец списка; дерево остаётся полным. Условие могло нарушиться только между новичком и его родителем. Если новичок меньше родителя — меняем их местами и смотрим на следующего родителя. Новичок всплывает, пока не упрётся в родителя меньше себя или не станет корнем. Это просеивание вверх.
Протащите ползунок под деревом. Единица пришла пятой: встала в ячейку 4 под четвёркой, поменялась с ней, потом с тройкой в корне и стала корнем за два обмена. Получившийся список [1, 3, 2, 5, 4, 9, 8] совсем не отсортирован — и не должен: куча обещает только, что наименьший первый.
Достать. Наименьший лежит в ячейке 0, отдаём его. Но на его месте дыра, а дыра в середине ломает полноту. Поэтому в корень переезжает последний элемент списка — его ячейка освобождается без всяких сдвигов, ведь pop() с конца стоит $O(1)$. Теперь нарушитель в корне: скорее всего, он больше своих детей. Меняем его с меньшим из детей — тогда новый родитель окажется не больше и второго ребёнка — и повторяем этажом ниже. Это просеивание вниз.
Семь извлечений наименьшего выдали числа по возрастанию, так что кучей можно и сортировать; к этому мы вернёмся. Сначала посчитаем, во что обходится каждая операция.
В куче из $n$ элементов добавление и извлечение наименьшего делают не больше $2\log_2 n$ сравнений.
Просеивание вверх на каждом шаге поднимается на этаж и делает одно сравнение; просеивание вниз опускается на этаж и делает два сравнения — с каждым из детей. Этажей в полном дереве из $n$ узлов $\lfloor \log_2 n \rfloor + 1$, так что подъём или спуск проходит не больше $\lfloor \log_2 n \rfloor$ этажей. Обмены, переезд последнего элемента и append стоят $O(1)$ на шаг.
Диспетчер на куче
Писать кучу самим каждый раз не нужно: в Python она уже есть, в модуле heapq. Класса там нет, только функции, которые работают с обычным списком так же, как наши push и pop: heapq.heappush(a, x), heapq.heappop(a), а a[0] — подсмотреть наименьший, не доставая. В CPython эти функции написаны на C. Повторим замер из попытки со списком на том же потоке больных, только коридором теперь будет куча.
Около микросекунды на одного — и при тысяче ждущих, и при миллионе. На ста тысячах куча обгоняет список больше чем в тысячу раз. Заметную часть этого времени, около пятой доли микросекунды, съедает сам randint, а двадцать этажей просеивания — это два-три десятка сравнений, мелочь.
Ключ — снова кортеж, и номер прихода в нём не для красоты. Если бы в кучу клали пары (категория, имя), то при равной категории кортежи начали бы сравнивать имена — и красную Анну позвали бы раньше красного Бориса, пришедшего на час раньше. А если вместо имени лежит объект, который сравнивать не умеет, например словарь с карточкой больного, heappush упадёт с TypeError. Счётчик прихода решает обе беды: он уникален, поэтому до третьего элемента сравнение не доходит никогда.
И ещё одна деталь heapq: это куча с наименьшим наверху. Если нужен наибольший — скажем, ключ «тяжесть», где 10 хуже 1, — в кучу кладут ключ с минусом: heappush(a, (-severity, number, card)). Самый тяжёлый станет самым «маленьким».
Построить за линейное время
В замере выше была строчка heapq.heapify(waiting): она превращает готовый список в кучу. Самое очевидное — добавлять элементы по одному через push: $n$ раз по $O(\log n)$, всего $O(n \log n)$. Так кучу строил её изобретатель. Есть способ быстрее, и устроен он почти наоборот.
Положим элементы в массив как есть — получится полное дерево, только без порядка. Листья — вторая половина массива — уже маленькие правильные кучи: под ними никого. Теперь пройдём по остальным узлам с конца к началу и каждый просеем вниз. Когда очередь доходит до узла, оба его поддерева уже кучи, и после просеивания кучей становится и всё поддерево узла. Последним просеивается корень — и куча готова. Это способ Роберта Флойда. Сравним оба на худшем для первого способа входе — числах по убыванию, где каждый новичок всплывает до самого корня.
По одному — 8, 11, почти 15 сравнений на элемент, и число растёт с логарифмом. Снизу вверх — не больше двух на элемент, сколько бы их ни было. Объясняет это короткий подсчёт: большая часть работы достаётся узлам, которым недалеко тонуть.
Просеивание вниз всех узлов от последнего родителя к корню превращает массив из $n$ элементов в кучу за $O(n)$ сравнений — точнее, меньше чем за $2n$.
Пусть под узлом $j$ этажей: у листа $j = 0$, у его родителя $j = 1$ и так далее. Такой узел при просеивании опускается не больше чем на $j$ этажей и на каждом тратит два сравнения — с двумя детьми. Узлов с данным $j$ в полном дереве примерно $n / 2^{j+1}$: листьев половина, их родителей четверть, следующих восьмая часть. Сумма по всем $j$:
$$\sum_{j \ge 1} \frac{n}{2^{j+1}} \cdot 2j \;=\; n \sum_{j \ge 1} \frac{j}{2^j} \;=\; n \left(\frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \frac{4}{16} + \ldots\right).$$Обозначим сумму в скобках $S$. Тогда $S - S/2 = \frac12 + \frac14 + \frac18 + \ldots = 1$: из каждого слагаемого $\frac{j}{2^j}$ вычлось $\frac{j-1}{2^j}$, остались чистые степени двойки. Значит, $S = 2$, и сравнений около $2n$. Аккуратный подсчёт с округлениями даёт ту же границу: на любом входе их меньше $2n$ — в замере выше 1982 на тысяче и 199 978 на ста тысячах.
У двух способов противоположная арифметика. Когда элементы добавляются по одному, самых многочисленных — тех, что пришли последними и лежат внизу, — ждёт самый длинный путь, до корня. У Флойда длинный путь только у корня и его ближайших потомков, а половина узлов — листья — не двигается вовсе. В виджете с кучей выше есть обе кнопки: постройте одну и ту же кучу двумя способами и сравните счётчики.
Пирамидальная сортировка
Сортировка из кучи напрашивается: построить кучу и $n$ раз достать наименьший. Это $O(n)$ на построение и $n$ раз по $O(\log n)$ на извлечения — всего $O(n \log n)$, столько же, сколько у сортировки слиянием, и в худшем случае тоже. Хитрость Флойда — обойтись без второго списка. После каждого извлечения куча становится на ячейку короче, и освободившаяся ячейка в конце массива как раз годится для ответа. Чтобы в конце копился ответ по возрастанию, кучу берут перевёрнутую: наверху наибольший. Код тот же, знак сравнения обратный.
Под ячейкой — массив на каждом шаге второй фазы: зелёный хвост — уже готовый ответ, слева от указателя — куча, которая с каждым шагом короче. Пирамидальная сортировка работает за $O(n \log n)$ всегда, на любом входе, и не требует дополнительной памяти, кроме пары переменных. У быстрой сортировки из главы 21 бывает квадратичный худший случай, слиянию нужен второй массив той же длины. Но и у кучи свои недостатки. Она прыгает по памяти от корня к далёким листьям, а процессор такого не любит (почему — в главе 34). И она неустойчива: равные элементы могут поменяться местами.
Поэтому в библиотеках пирамидальная сортировка служит страховкой. Сортировка std::sort во многих реализациях C++ — это introsort: быстрая сортировка, которая следит за глубиной рекурсии и, если та подозрительно растёт, переключается на пирамидальную. Худший случай быстрой сортировки становится невозможен, а в обычных случаях работает быстрая.
Десять сильнейших из потока
В главе 6 мы нашли десять сильнейших землетрясений каталога: отсортировали все 19 073 толчка и взяли первые десять. А в задаче «Первые k» обещали способ быстрее, и он держится на куче. Пусть толчки идут потоком, один за другим, как они происходили с 2015 года. Держим кучу из $k$ лучших на текущий момент — кучу с наименьшим наверху. Тогда в корне лежит самый слабый из лучших: планка, которую надо перепрыгнуть. Новый толчок сравниваем с корнем. Слабее планки — проходит мимо, одно сравнение. Сильнее — выталкивает корень и занимает место в куче, $O(\log k)$.
В каталоге 19 073 толчка, они идут по времени. Сколько раз, по-вашему, изменится табло десяти сильнейших — считая и первые десять, которые заполняют пустое табло?
84 раза — проверьте ниже. Если бы толчки шли в случайном порядке, среднее число смен табло было бы около $k\,(1 + \ln (n/k))$, для $k = 10$ и $n = 19\,073$ — примерно 85. Новый рекорд среди многих — редкость, и чем дальше, тем реже.
heapreplace делает два дела за одно просеивание: достаёт корень и кладёт новый элемент. Время — $O(n \log k)$ вместо $O(n \log n)$ у сортировки. Ещё ценнее выигрыш в памяти: куче нужно $k$ ячеек, и весь каталог держать незачем. Поэтому поток может быть бесконечным, как генератор из главы 10, или не помещаться в память, как журнал запросов сервера за год или все ставки на бирже.
Если поток идёт по возрастанию, планка ползёт вверх вместе с ним, и табло меняется постоянно. Будь все магнитуды разными, каждый новый толчок выталкивал бы корень — это худший случай, $n \log k$ сравнений. У нас магнитуды почти все округлены до десятых, а толчок, равный планке, не проходит, поэтому при $k = 10$ смен 427 — в пять раз больше, чем по времени, но далеко не 19 073. Если поток идёт по убыванию, табло заполняется первыми $k$ толчками и больше не меняется. Живые данные обычно похожи на перемешанные: планка быстро взлетает, а дальше почти все проходят мимо за одно сравнение.
В heapq это уже написано: heapq.nlargest(10, quakes, key=lambda q: q[4]) и heapq.nsmallest работают именно так. Там же лежит heapq.merge — слияние нескольких отсортированных потоков в один: куча держит по одному, текущему элементу из каждого потока, и наименьший из них — следующий в ответе. На этом приёме построена одна из задач главы.
Календарь событий
Осталось заглянуть внутрь приёмного покоя из начала главы: откуда программа знает, что случится дальше? Остров кроликов и лис из главы 12 жил по тактам: каждый день все звери делают ход. Приёмный покой так считать расточительно. Больной приходит раз в несколько минут, лечение длится полчаса, и в большинство минут не происходит ничего. Поэтому программа прыгает от события к событию.
Событий здесь два: «пришёл больной» и «врач освободился». Каждое — пара (время, что случилось), и все будущие события лежат в куче по времени. Программа достаёт ближайшее, переводит часы на его время, обрабатывает его — и при этом может положить в кучу новые события: позвали больного — значит, через столько-то минут врач освободится. Это событийное моделирование, и в нём две очереди с приоритетом: календарь событий по времени и коридор по срочности. Весь приёмный покой умещается в полсотни строк; ниже он прогоняет одни и те же сутки с тремя разными диспетчерами.
Шесть больных в час для двух врачей — плотный, но посильный день. «По приходу» все ждут примерно поровну, около четверти часа, и красные тоже. «По тяжести» красные и оранжевые ждут две-три минуты, а синие — полчаса в среднем и почти три часа дольше всех. Ларрей был бы доволен.
Восемь в час — больше, чем двое врачей успевают принять, и коридор растёт весь день. Теперь «по тяжести» синий больной ждёт в среднем восемь часов, а самый невезучий — пятнадцать с половиной. Пока приходят срочные, несрочного не позовут никогда. Это явление называют голоданием, и оно подстерегает любую очередь с приоритетом под нагрузкой.
Третье правило, «по сроку», лечит голодание одной строчкой. Ключом служит момент, когда истекает норма ожидания: время прихода плюс 0, 10, 60, 120 или 240 минут. Красный, пришедший сейчас, всё равно впереди почти всех. Но синий, прождавший четыре часа, обгонит только что пришедшего жёлтого: его срок истёк раньше. Бесконечно теперь не ждёт никто. Платят за это сами срочные: при восьми больных в час красные ждут уже 10 минут вместо 6. При этом ключ со временем не меняется, срок каждого больного известен в момент прихода. Куче не нужно ничего пересчитывать, хотя по смыслу приоритет растёт с ожиданием.
Компьютер решает такую же задачу непрерывно. Планировщик операционной системы выбирает, какая из сотен программ получит процессор в следующую миллисекунду, и тоже должен не уморить голодом фоновые задачи, — его мы построим в главе 37. В язык Simula из главы 12 календарь событий был встроен с рождения: там он называется sequencing set, и события в нём стоят по возрастанию времени. А куча ещё вернётся в курс дважды: в главе 23 она будет склеивать коды Хаффмана из двух самых редких букв, а в главе 24 — подсказывать навигатору, какой перекрёсток ближе всего.
Задачи
Четыре задачи на четыре приёма главы: своя очередь с приоритетом, k лучших, слияние потоков и две кучи сразу. Тесты проверяют края — пустые входы, повторы, ничьи — и большие входы с лимитом времени.
Напишите класс PriorityQueue — очередь с приоритетом на собственной куче, без модулей heapq и bisect и без сортировок:
push(item, priority)— добавить элемент с приоритетом (число; меньше — срочнее);pop()— достать и вернуть элемент с наименьшим приоритетом, а среди равных — тот, что добавлен раньше;peek()— вернуть его же, не доставая;len(q)— сколько элементов в очереди.
pop и peek у пустой очереди поднимают IndexError. Элементы могут быть чем угодно, в том числе словарями, которые не умеют сравниваться. Двести тысяч операций должны укладываться в четыре секунды.
Заготовка — это «попытка первая» из главы, и у неё две беды. Найдите обе: что будет при равных приоритетах, если элементы — словари? И сколько стоит pop?
Храните в куче тройки (приоритет, номер добавления, элемент). Номер — счётчик, который растёт с каждым push: он делает ключи уникальными, поэтому до сравнения самих элементов дело не дойдёт, а равные приоритеты выйдут в порядке добавления.
Просеивание вверх и вниз — как в ячейках «добавить.py» и «достать.py». Не забудьте случай, когда в куче один элемент: после pop() последнего переносить в корень некого.
Сравнение срезов a[i][:2] — пар (приоритет, номер) — подчёркивает, что элемент не участвует в сравнении вовсе. Сравнивать целые тройки тоже можно: номера уникальны, и кортеж решится на втором элементе. Так и советует делать документация heapq.
Напишите k_smallest(stream, k): вернуть список из k наименьших чисел потока по возрастанию (если чисел меньше k — все). Поток — любой перебираемый объект, в том числе генератор, который можно пройти только один раз; в тестах в нём бывает два миллиона чисел. Пользоваться sorted, .sort(), heapq.nsmallest и heapq.nlargest нельзя: решите кучей из главы. heappush, heappop и heapreplace — можно.
Это табло из раздела про землетрясения, только наоборот: держим $k$ наименьших, а планка — самый большой из них. Нужна куча с наибольшим наверху. В heapq такой нет — кладите числа с минусом.
Новое число входит, только если оно меньше планки: x < -heap[0]. Тогда heapq.heapreplace(heap, -x).
В конце куча содержит ответ, но не по порядку. heappop отдаёт наименьшее из минус-чисел, то есть наибольшее из ваших: соберите все и разверните. Случай k = 0 проверьте отдельно.
Время — $O(n \log k)$, память — $O(k)$, поток читается один раз. Для двух миллионов чисел и $k = 10$ почти все числа отсеиваются одним сравнением с планкой.
На сервере тысяча журналов, каждый уже отсортирован по времени. Напишите merge_sorted(lists): получить список списков, каждый отсортирован по возрастанию, и вернуть один общий отсортированный список. Списки бывают пустыми и разной длины, числа повторяются. Пользоваться sorted, .sort() и heapq.merge нельзя. В тестах — две тысячи списков, вместе четыреста тысяч чисел: сравнивать на каждом шаге головы всех списков не успеет.
Заготовка верна, но на каждом шаге смотрит на все $k$ голов: $O(N \cdot k)$. Головы надо держать в куче — тогда наименьшая из них находится за $O(\log k)$.
В кучу кладите тройки (значение, номер списка, позиция в списке). Достали тройку — значение в ответ, а в кучу — следующий элемент того же списка, если он есть.
Каждое из $N$ чисел один раз входит в кучу и один раз выходит: $O(N \log k)$. Номер списка в тройке нужен, чтобы при равных значениях знать, откуда брать следующее, — и чтобы сравнение не дошло до чего-то несравнимого. Так сливают отсортированные куски данных, которые не помещаются в память: каждый кусок сортируют отдельно, потом сливают кучей. Если поменять heappop и heappush на одну heapreplace, станет ещё чуть быстрее.
Датчик присылает числа одно за другим, и после каждого надо знать медиану всех присланных. Напишите running_median(numbers), которая возвращает список медиан: $i$-й элемент — медиана первых $i + 1$ чисел. При нечётном количестве медиана — средний по величине элемент, при чётном — среднее арифметическое двух средних. Например, running_median([5, 15, 1, 3]) → [5, 10.0, 5, 4.0]. В тестах — четыреста тысяч чисел; сортировать после каждого числа или вставлять в отсортированный список не успеет.
Разделите прочитанные числа на две половины: меньшую и большую. Медиана — на границе: наибольшее из меньшей половины и наименьшее из большей. Нужна куча с наибольшим наверху для меньшей половины (числа с минусом) и обычная куча для большей.
Поддерживайте два правила: всё в нижней куче не больше всего в верхней, и нижняя больше верхней не больше чем на один элемент. Новое число кладите в нижнюю, потом перебросьте её наибольшее в верхнюю, а если верхняя стала больше — перебросьте её наименьшее обратно.
На каждое число приходится не больше пяти операций с кучами — три heappush и два heappop, каждая за $O(\log n)$, так что всё вместе стоит $O(n \log n)$, а медиана в любой момент лежит в корне одной из куч. Перебрасывание через верхнюю кучу кажется лишним, но оно гарантирует первое правило: в нижнюю попадает только то, что не больше всего в верхней.
Куда дальше
Всё, что мы до сих пор раскладывали по структурам, жило поодиночке: больной в коридоре, толчок в каталоге, слово в словаре. Даже в дереве у каждого узла один начальник, и путь между двумя узлами единственный. Но данные бывают связаны. Друзья знакомы с друзьями друзей, и знакомства идут кругами. Станции метро соединены перегонами и пересадками, и из одной в другую ведёт сотня дорог. Страницы сайта ссылаются друг на друга, главы этого учебника — на главы, которые надо прочесть раньше. Про такие данные спрашивают уже не «кто следующий», а «как отсюда дойти туда и за сколько шагов». Говорят, что любые два человека на Земле знакомы через шесть рукопожатий. В следующей главе мы это проверим — на московском метро и на самом этом курсе.