В реализации турнирного дерева используется дополнительное пространство, так как данные для сравнения устанавливаются на листьях дерева, а затем сравниваются. Я читал, что это полезно, когда нам нужно объединить k отсортированных массивов. Теперь предположим, что мы хотим объединить k отсортированных массивов. Если вместо сохранения фактических значений я сохраняю индексы и создаю минимальную кучу, а затем использую пользовательскую функцию сравнения в реализации min_heap, которая сортирует значения по этому индексу. Благодаря этому мы можем узнать, какой следующий элемент будет добавлен в кучу. Разве это не было бы лучшей реализацией, поскольку это сэкономило бы половину нашего пространства? Кроме того, временная сложность также будет такой же. Разве приведенная выше реализация не лучше, чем подход с использованием дерева турниров?
Тогда в каких случаях дерево турниров может быть полезным?
В каких случаях дерево турниров (Дерево победителей) может быть полезным?
comment
Вы читали geeksforgeeks.org/tournament-tree-and-binary-heap< /а> ?
- person Jim Mischel schedule 14.02.2018
comment
Итак, в основном я сокращаю количество сравнений в обмен на пространство.
- person shiwang schedule 14.02.2018
comment
И я думаю, что это реализовано так же, как я написал. т.е. сохраняя индексы, а не фактические значения. Благодаря этому мы можем узнать, из какого массива нам нужно добавить следующий элемент в кучу. @JimMischel
- person shiwang schedule 14.02.2018
Ответы (1)
Деревья турниров полезны для турнирной сортировки, которая часто используется для N-путевых слияний, а иногда для внешней сортировки. Турнирная сортировка считается разновидностью пирамидальной сортировки.
Другим приложением является поиск медианы нескольких отсортированных массивов или поиск верхних (или нижних) k элементов в списке.
Турнирное дерево — это не замена двоичной кучи, а специальное использование двоичной кучи.
person
Jim Mischel
schedule
14.02.2018
