При реализации дерева турниров, дополнительное пространство используется в качестве данных для сравнения, устанавливается на листьях дерева и затем сравнивается. Я читал, что это полезно, когда нам нужно объединить k отсортированных массивов. Теперь давайте предположим, что мы хотим объединить k отсортированных массивов. Если вместо сохранения фактических значений я сохраняю индексы и создаю минимальную кучу, а затем использую пользовательскую функцию сравнения в реализации min_heap, которая сортирует по значениям в этом индексе. По этому мы можем знать следующий элемент, который будет добавлен в кучу. Разве это не будет лучшей реализацией, так как это сэкономит половину нашего пространства? Более того, сложность времени также будет такой же. Разве вышеприведенная реализация не лучше, чем подход дерева турниров?
Тогда какие могут быть случаи, когда дерево турниров может быть полезным?
Турнирные деревья полезны для турнирная сортировка, который часто используется для N-way слияний, а иногда и для внешней сортировки. Турнирная сортировка считается вариантом heapsort.
Другое приложение находит медиану нескольких отсортированных массивов или находит верхние (или нижние) k элементов в списке.
Турнирное дерево — не замена бинарной кучи, а конкретное использование бинарной кучи.
Других решений пока нет …