Tournament Sort

Проблема

Обычная сортировка выбором находит минимум оставшейся части массива за O(n) проходом, повторяя это n раз, что даёт O(n²). При этом информация о сравнениях, сделанных на предыдущем проходе, полностью выбрасывается - на следующем проходе всё сравнивается заново. Нужен способ переиспользовать результаты прошлых сравнений, чтобы находить следующий минимум быстрее.

Решение

Все элементы становятся листьями полного бинарного дерева (дерева турнира). Каждый внутренний узел хранит индекс «победителя» - меньшего из двух потомков, как в турнирной сетке на выбывание. Корень дерева всегда содержит глобальный минимум. После извлечения минимума его лист заменяется на +∞, и обновить дерево нужно только вдоль пути от этого листа до корня - O(log n) вместо O(n). Повторяя это n раз, получаем полностью отсортированный массив за O(n log n).

Как это работает

Дерево турнира хранит в каждом внутреннем узле не значение, а индекс листа-победителя. Это важное отличие от кучи: в min-heap узел содержит само значение и теряет связь с исходной позицией элемента, а в дереве турнира можно всегда узнать, *какой именно* элемент сейчас в корне, не теряя его исходный индекс.

Построение дерева - это ровно один проход снизу вверх: цикл идёт от последнего внутреннего узла (индекс size - 2) до корня (индекс 0). У любого узла с таким индексом оба потомка уже вычислены раньше в этом же проходе (они либо листья, либо узлы с большим индексом), поэтому каждый узел считается ровно один раз - O(n) сравнений всего, без единого повторного обхода пути.

На массиве из 1000 случайных элементов (дополненном до size = 1024) построение занимает ровно 1023 сравнения - это size - 1, столько же, сколько внутренних узлов в дереве. Наивная альтернатива - вызывать пересчёт пути от каждого листа до корня по отдельности - дала бы 10240 сравнений (n·log₂(size)) на построение, то есть в 10 раз больше, вырождая заявленное O(n) в фактическое O(n log n).

После построения каждое извлечение минимума требует пересчёта только пути от изменённого листа до корня - O(log n) сравнений. На том же массиве из 1000 элементов это даёт 10000 сравнений на все n извлечений (n · log₂(size)), что вместе с построением суммарно даёт около 11000 сравнений - тот же порядок, что и n · log₂(n) ≈ 9966.

Дополнение массива фиктивными +∞-листьями до ближайшей степени двойки (например, 9 элементов дополняются до 16) гарантирует, что дерево - полное бинарное дерево: у каждого внутреннего узла ровно два потомка, без особых случаев для "неполного последнего уровня". Фиктивные листья никогда не побеждают ни в одном сравнении и просто не попадают в вывод.

Дерево турнира структурно эквивалентно priority queue поверх фиксированного набора элементов: операция "извлечь минимум и обновить" - это ровно extract-min из очереди с приоритетом. Разница с min-heap - не в асимптотике (обе O(log n) на операцию), а в том, что дерево турнира явно хранит результаты всех прошлых парных сравнений в виде дерева, а не только частичный порядок в массиве кучи.

Нюансы выбора

По сравнению с heap sort: если важна память и in-place сортировка, heap sort выигрывает - он не создаёт отдельную структуру. Дерево турнира оправдано, когда нужен явный доступ к дереву сравнений между операциями, а не только к текущему минимуму.

По сравнению с обычным min-heap: дерево турнира предпочтительнее, когда важно явно видеть путь сравнений, приведших к победителю (например, для отладки турнирной логики или визуализации "кто с кем сравнивался") - min-heap этого не хранит.

В k-путевом слиянии (внешняя сортировка, слияние N потоков): дерево турнира естественно масштабируется - каждый "лист" представляет текущую голову одного потока, и обновление после извлечения затрагивает только O(log k) узлов вместо сравнения всех k голов заново.

Крайний случай - очень маленький n (например, n ≤ 4): накладные расходы на построение дерева (дополнение до степени двойки, отдельный массив winner) не окупаются, и обычная сортировка вставками отработает быстрее на практике при одинаковой корректности результата.

Примеры в коде

Внешняя сортировка больших файлов (Донald Кнут, "The Art of Computer Programming", том 3, раздел 5.4.1) использует winner tree в форме турнирного дерева для слияния десятков и сотен отсортированных фрагментов за один проход, не помещающихся в память целиком.

Реляционные базы данных используют аналогичные структуры (replacement selection + tournament tree) в операторах ORDER BY/MERGE JOIN, когда промежуточный результат сортировки не помещается в буфер памяти и требует слияния временных файлов на диске.

Симуляции спортивных турниров и матчмейкинг-системы (например, рейтинговые системы на основе single-elimination bracket) используют структуру дерева турнира буквально - не как метафору сортировки, а как модель реального турнира с обновлением после каждого матча.

k-way merge в MapReduce/Hadoop shuffle-фазе использует ту же идею для слияния отсортированных выходов множества мапперов перед подачей на редьюсер - без tournament-tree пришлось бы сравнивать все k текущих голов при каждом выборе следующего элемента.

Когда применять

• Когда нужно многократно находить и удалять минимум из динамически меняющегося набора - не только для одноразовой сортировки, но как структура данных (winner tree).
• Как учебный мост между сортировкой выбором и приоритетными очередями/кучами: помогает понять, зачем вообще нужна O(log n) структура для повторного извлечения минимума.

Примеры из практики

• Внешняя сортировка (external merge sort) использует winner tree именно в форме турнирного дерева для k-путевого слияния множества отсортированных файлов с диска за один проход.
• Системы обработки потоковых данных, где нужно постоянно поддерживать «текущий минимум/максимум» среди активных элементов с эффективным обновлением.