Двоичная куча

В коробке сто пятьдесят дисков. Каждый летит по прямой и отскакивает от стенок и от соседей, а программе нужно знать одно: что случится раньше всего. Двигать все диски понемногу и проверять, не налетели ли они друг на друга, долго и неточно — при крупном шаге диски проскакивают друг сквозь друга. Поэтому программа заранее вычисляет для соседних дисков момент удара, а для каждого диска — момент, когда он долетит до стенки, и записывает всё это в календарь. Дальше она раз за разом берёт из календаря самую раннюю запись, и ничего, кроме этого, ей от календаря не нужно. Календарь — двоичная куча, и рядом с коробкой видна её вершина.

На отметке t = 10 сцена останавливается: к этому моменту программа достала из кучи 34 103 записи, и 22 279 из них, почти две трети, оказались устаревшими. Прогноз «эти два диска столкнутся в момент 4,317» перестаёт быть правдой, как только один из них раньше налетел на третий. Разыскивать и удалять такие записи программа не стала — она выбросила каждую, когда та сама всплыла наверх. Настоящих событий набралось 11 824: 3061 столкновение, 937 отскоков от стенок и 7826 переходов через линии сетки (зачем сетка, расскажем в разделе с кодом). Куча разрослась до 1600 записей, и все её операции стоили 679 тысяч сравнений. Будь календарь обычным списком, в котором ближайшую запись ищут просмотром, понадобилось бы 46,7 миллиона сравнений — почти в 69 раз больше.

Посмотрите и на гистограмму. В начале у всех дисков одна скорость, 0,5, и столбик стоит один. К t ≈ 2 удары перемешивают скорости, и гистограмма ложится на кривую, которую в 1860 году вывел Джеймс Клерк Максвелл, — точнее, на её вариант для плоскости. Случайных чисел после старта в программе нет: распределение получается из одной механики упругих ударов.

Идея

Двоичная куча — полное двоичное дерево, в котором каждый узел не больше своих детей. Отсюда наименьший элемент всегда в корне. Дерево лежит в массиве без единого указателя: дети ячейки i — ячейки 2i + 1 и 2i + 2, родитель — ячейка ⌊(i − 1)/2⌋. Добавить элемент или достать наименьший — значит починить порядок вдоль одного пути от корня к листу, а длиннее log₂ n такой путь не бывает.

Условие «родитель не больше детей» называют свойством кучи. Оно на удивление слабое. Братья между собой не упорядочены, соседние ветви друг другу не указ, и найти в куче произвольное значение так же трудно, как в мешке. Зато порядок по вертикали — от корня к любому листу ключи не убывают — даёт ровно то, что нужно календарю: самая ранняя запись наверху. Отсортированный массив и дерево поиска хранят полный порядок и платят за него: вставка в середину массива сдвигает хвост, дерево поиска держит указатели и балансирует себя поворотами. Куче полный порядок не нужен, и она за него не платит.

Полнота дерева — второе условие: этажи заполняются сверху вниз, а последний — слева направо без дыр. Поэтому дерево из n узлов всегда настолько низкое, насколько возможно, выродиться в палку ему нечем, и номера ячеек сами задают связи. Если ключи надо доставать от большего к меньшему, знак сравнения меняют на обратный. В Python модуль heapq долго умел только кучу с минимумом наверху, и наибольшее доставали, кладя ключи с минусом; функции heappush_max, heappop_max и их соседи появились в версии 3.14. Подробное знакомство с кучей на примере приёмного покоя — в главе курса «Кто следующий»; здесь — устройство, доказательства и то, что нужно на практике.

Просеивание

Все операции кучи сводятся к двум движениям. Вверх: элемент, который оказался меньше родителя, меняют с ним местами, пока он не упрётся в родителя не больше себя или не станет корнем. Вниз: элемент, который оказался больше кого-то из детей, меняют с меньшим из детей — тогда новый родитель не больше и второго ребёнка, — пока порядок не восстановится или пока не кончится дерево.

• Добавить — положить в конец массива (дерево остаётся полным) и просеять вверх.
• Достать минимум — забрать корень, поставить на его место последний элемент массива и просеять его вниз.
• Изменить ключ — записать новый и просеять: вверх, если ключ уменьшился, вниз, если вырос.
• Удалить из середины — поставить на освободившееся место последний элемент и просеять его вверх или вниз, смотря куда он не помещается.

Две последние операции требуют знать, в какой ячейке лежит элемент. Куча этого не знает: при каждом обмене элементы переезжают. Поэтому рядом с массивом держат второй, обратный — «где лежит» — и обновляют его при каждом обмене. Ниже — таймеры сервера: имя и через сколько секунд сработать. Это та же куча, что в программе timers из раздела с кодом.

Попробуйте отменить таймер из середины: на его место встанет последний из массива, и куда он поедет — вверх или вниз, — зависит от того, в какой ветви он лежал раньше. Переключите кучу на четверичную: этажей станет меньше, но на каждом этаже придётся сравнить уже четырёх детей. А потом снимите галочку «просеивать» и сделайте какой-нибудь нижний таймер раньше всех. Ребро к нему покраснеет, и «Сработать» выдаст таймеры не по порядку: куча не проверяет свойство, она его только поддерживает.

Почему это верно и почему логарифм

Есть и третья операция, которая работает быстрее, чем можно ожидать: построить кучу из готового массива. Если добавлять элементы по одному, выйдет n раз по O(log n). Роберт Флойд в 1964 году предложил делать наоборот: просеять вниз каждый узел, у которого есть дети, начиная с последнего и заканчивая корнем. Когда очередь доходит до узла, оба его поддерева уже кучи — это и есть начальное условие утверждения выше.

Половина узлов — листья, им тонуть некуда; четверть опускается не больше чем на этаж; и только корню может достаться весь путь. Сумма ⌊n/2⌋ + ⌊n/4⌋ + … , кстати, считается точно: она равна n минус число единиц в двоичной записи n — это формула Лежандра для степени двойки в n!. Для десяти таймеров (1010 в двоичной записи) сумма высот — 8, сравнений не больше 16, а в программе ниже их 12.

Как отменить таймер

Учебная куча умеет добавлять и доставать. Настоящему календарю этого мало: таймаут запроса обычно отменяют, потому что ответ пришёл раньше; соединение, по которому идёт обмен, каждый раз откладывает свой таймер простоя; в газе каждый удар делает неверными прогнозы двух дисков. Элемент приходится убирать из середины кучи, а куча не знает, где он. Способов справиться два, и оба работают в стандартных библиотеках.

Пометить и забыть. Запись не трогают, а помечают как недействительную; когда она всплывёт наверх, её молча выбросят. Это ленивое удаление. В газе пометка даже не нужна: каждая запись помнит, сколько раз её диски меняли курс к моменту прогноза, и если с тех пор счётчик вырос, прогноз устарел. Так же устроен календарь в алгоритме Дейкстры: перекрёсток, до которого нашли путь короче, просто кладут в кучу ещё раз. Плата — память и лишние извлечения: в газе две трети работы кучи уходит на мусор. Поэтому ленивые кучи время от времени чистят:

• в asyncio отменённый таймер только помечается, цикл событий выбрасывает такие таймеры с вершины кучи, а когда в куче больше ста таймеров и больше половины из них отменены, собирает новую кучу из живых — за O(n), функцией heapify;
• в рантайме Go остановленный таймер становится «зомби» и остаётся в куче своего процессора; зомби вычищают по дороге, а если их больше четверти, кучу перебирают целиком;
• документация heapq советует тот же рецепт: держать словарь «задача → запись», при отмене заменять задачу в записи меткой REMOVED, а при смене приоритета класть новую запись.

Знать, где лежит. Каждый элемент помнит номер своей ячейки, и каждый обмен этот номер обновляет. Тогда отмена и перенос стоят O(log n): на освободившееся место — последний элемент, и просеять. В Go так устроен пример из документации container/heap: у элемента есть поле index, а функции heap.Fix и heap.Remove принимают номер ячейки. В Java так хранит отложенные задачи ScheduledThreadPoolExecutor: каждая задача записывает свой номер в куче, и, как сказано в комментарии к исходному коду, это сокращает удаление с O(n) до O(log n). Причём по умолчанию отменённая задача всё равно лежит в очереди, пока не истечёт её срок, — немедленное удаление включается отдельной настройкой с Java 7.

Код

Сначала куча таймеров из сцены. В Go она построена на container/heap: тип реализует пять методов интерфейса, а Swap заодно обновляет поле index. В Python у heapq нет способа узнать, куда переехал элемент, поэтому класс написан с нуля — и повторяет шаг в шаг то, что делает container/heap, вплоть до порядка сравнений. Отсюда одинаковый вывод и одинаковые счётчики сравнений.

Перенос таймера H с 55 секунд на 2 стоил трёх сравнений — по одному на этаж, пока H поднимался к корню. Отмена E — одного: на место E встал последний таймер, B31, вниз ему было некуда, а вверх не понадобилось. Строка slots — тот самый обратный массив «где лежит».

Теперь газ из первой сцены. Календарь — heapq в Python и container/heap в Go, запись — кортеж (время, номер, вид события, диски, счётчики их ходов). Номер записи нужен, чтобы при равном времени сравнение не дошло до остальных полей. Положение диска хранится на момент его последнего события: между событиями диск летит по прямой, и пересчитывать все диски на каждом шаге незачем.

Остаётся вопрос, с кем предсказывать столкновения. Если с каждым, после каждого удара придётся перебирать все диски — так в 1959 году и считали. Программа делит коробку на клетки 10 × 10, не меньше диаметра диска: столкнуться могут только диски из соседних клеток. Переход диска через линию сетки — тоже событие календаря: в новой клетке у диска новые соседи, и с ними нужно составить прогнозы. Отсюда 7826 переходов из 11 824 событий: дешёвые события, которые экономят перебор всей коробки.

Обратите внимание на функцию mul в версии на Go. Спецификация языка разрешает компилятору склеивать умножение со сложением в одну инструкцию FMA, которая округляет один раз вместо двух; на процессорах ARM компилятор так и делает. Явное преобразование float64(a * b) это запрещает. Без него та же программа на Mac с процессором ARM достаёт к t = 10 из кучи 34 081 запись вместо 34 103 и насчитывает 3037 столкновений вместо 3061. Разница начинается в последнем бите одного числа, но газ хаотичен: каждый удар усиливает расхождение, и через сотню ударов история другая. Энергия при этом сохраняется в обоих вариантах до двенадцатого знака — физике всё равно, какая из двух историй случилась.

Сколько это стоит

Память — сам массив, O(n), без указателей и без служебных полей; если нужен перенос и отмена, добавляется обратный массив «где лежит». Последняя строка таблицы — слабое место двоичной кучи: две кучи нельзя слить быстрее, чем построив новую. Если слияние нужно часто, есть кучи на указателях — левосторонние, биномиальные, фибоначчиевы, — которые сливают за O(log n) и быстрее, но в обычной работе они медленнее массива.

Асимптотика говорит не всё. Ниже замер модели, которой проверяют календари событий: достать ближайшее событие и запланировать новое чуть позже, и так много раз подряд при неизменном числе n событий в календаре. Три календаря: куча, отсортированный массив, где ближайшее лежит с краю, а новое вставляется на своё место, и неупорядоченный массив, где ближайшее ищут просмотром.

Куча почти не замечает роста: от сотни до миллиона событий время на Go растёт вдвое, на Python — тоже вдвое, хотя этажей стало втрое больше. Просмотр растёт линейно и на больших календарях проигрывает куче в тысячи раз. Интереснее всего отсортированный массив. Его вставка тоже линейна, но это один сдвиг памяти, который процессор делает очень быстро. На сотне событий он вдвое обгоняет кучу на Go и чуть-чуть — на Python, на тысяче идёт почти вровень, и только дальше линейный рост берёт своё: на десяти тысячах — в пять раз медленнее кучи, на миллионе — в сотни раз. Для календаря на десяток таймеров куча не нужна; для календаря газа из тысяч дисков без неё никак.

Где работает

Куча — стандартная очередь с приоритетом почти во всех языках: heapq в Python, container/heap в Go, PriorityQueue в Java (в исходнике прямо сказано: сбалансированная двоичная куча, дети ячейки n — в ячейках 2n + 1 и 2(n + 1)), std::priority_queue в C++. На ней держатся Дейкстра, Прим и A*, код Хаффмана, отбор k лучших из потока, слияние отсортированных файлов во внешней сортировке (его разбирает задача о региональных каталогах), пирамидальная сортировка. И все календари событий: таймеры asyncio и рантайма Go, отложенные задачи Java, событийные модели — от очереди в банке до молекулярной динамики.

Двоичная куча — частный случай d-кучи, где у каждого узла d детей: родитель ячейки i — ⌊(i − 1)/d⌋, дети — di + 1, …, di + d. Этажей становится log_d n: просеивание вверх дешевеет, а вниз на каждом этаже стоит d сравнений. Рантайм Go держит таймеры в четверичной куче — в исходнике это константа timerHeapN = 4. Большое сравнение очередей с приоритетом, которое в 2014 году провели Дэниел Ларкин, Сиддхартха Сен и Роберт Тарьян, показало, что время работы куч сильнее всего связано с промахами кэша первого уровня: на сортировке быстрее всех оказалась простая четверичная куча в массиве, на алгоритме Дейкстры по дорожной сети целой страны четверичная куча тоже была среди лучших, а фибоначчиева — примерно втрое медленнее. Переключатель «четверичная» во второй сцене показывает, откуда выигрыш: этажей меньше, а соседние дети лежат в памяти рядом.

Список Алдера и Уэйнрайта

В 1957 году Берни Алдер и Томас Уэйнрайт опубликовали расчёт, с которого начинается молекулярная динамика: машина прослеживала движение нескольких сотен твёрдых шаров, и результат указывал, что даже шары без всякого притяжения друг к другу переходят из жидкого состояния в кристалл. В статье 1959 года они описали метод. Для каждой пары шаров вычисляется момент столкновения, все шары переносятся к самому раннему, и двое столкнувшихся меняют скорости. Дальше не надо пересчитывать всё: достаточно проверить пары, в которых участвует один из двух шаров, — их 2N − 3. Прогнозы, где фигурируют эти два шара, вычёркиваются: они, как сказано в статье, сделаны в ошибочном предположении, что шары не столкнутся. Это то же ленивое устаревание, что в нашей первой сцене, только календарём служил список.

Машина UNIVAC успевала около сотни столкновений в час для сотни шаров; IBM 704 — около двух тысяч в час для ста шаров и около пятисот для пятисот. Как защиту от сбоев машины авторы проверяли полную энергию, которая должна оставаться постоянной, — та же строка есть в выводе нашей программы. Там же они предложили на будущее делить ящик на клетки и проверять только соседей. Версия нашей программы на JavaScript, которая работает в первой сцене, на обычном ноутбуке обсчитывает около двухсот тысяч столкновений в секунду.

Сама куча появилась в 1964 году: в июне в Communications of the ACM вышла заметка Дж. У. Дж. Уильямса «Algorithm 232: Heapsort», где куча была описана как структура данных сама по себе, а в декабре Роберт Флойд напечатал «Treesort 3» с построением снизу вверх за линейное время. История Уильямса — в главе курса. Через десять лет кучу снова стали улучшать, теперь ради графов: в алгоритмах Дейкстры и Прима главная операция — уменьшить ключ, и Дональд Джонсон в 1975 году предложил d-кучи, у которых эта операция дешевле; заголовок его статьи так и звучит — «Очереди с приоритетом с обновлением и поиск минимальных остовных деревьев». В 1984 году Майкл Фредман и Роберт Тарьян придумали фибоначчиевы кучи, где уменьшение ключа стоит O(1) в среднем по последовательности операций, и Дейкстра получил оценку O(E + V log V). На бумаге это лучше, а на практике, как показал замер тридцать лет спустя, массив снова оказался быстрее.

Задачи

В первой задаче таймеры продлеваются и отменяются, а данные одного из тестов — настоящий каталог землетрясений USGS. Во второй куч две, и из обеих приходится удалять — лениво; данные — 85 лет погоды Алматы.