В каких случаях может помочь дерево турниров (Winner Tree)?

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

0

Решение

Турнирные деревья полезны для турнирная сортировка, который часто используется для N-way слияний, а иногда и для внешней сортировки. Турнирная сортировка считается вариантом heapsort.

Другое приложение находит медиану нескольких отсортированных массивов или находит верхние (или нижние) k элементов в списке.

Турнирное дерево — не замена бинарной кучи, а конкретное использование бинарной кучи.

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]