Tournament Tree for Finding Two Maximums in an Array

Russian version at the bottom of the page.

Efficient Maximum Search in a Tournament Tree is a great way to find the maximum element in a sequence of numbers. Let's explore it in more detail.

Tournament Tree: The first step is to construct a tournament tree. This is a binary tree in which each node represents a comparison between two elements. In each node, the index of the winner (the element with the highest value) of the two compared elements is stored.

Construction of the Tournament Tree: To find the maximum in a sequence of length n, you begin by constructing a tournament tree from these n elements. Typically, you use a data structure that can be represented as an array, where each array element corresponds to a tree node.

Comparisons in the Tournament Tree: Comparisons occur at each level of the tree. At each level, a winner is selected from a pair of adjacent elements and moves on to the next level of the tree. This process is repeated until the final winner is found, representing the maximum element in the sequence.

Number of Comparisons: The number of comparisons required to find the maximum depends on the number of elements in the sequence. If n is a power of two, it will take log2(n) comparisons to find the maximum. This is because each comparison reduces the number of remaining elements by half.

For example, for n = 8, as in your example, it would take log2(8) = 3 comparisons to find the maximum.

Link to the GitHub with the code is at the bottom of the page.

• Python version

p = [3, 1, 4, 1, 5, 9, 2, 6]


def tournament_two(A):
    N = len(A)
    winner = [None] * (N - 1)  # Winner at each level
    loser = [None] * (N - 1)  # Loser at each level
    prior = [-1] * (N - 1)  # Previous winners
    idx = 0

    # Tournament tree construction
    for i in range(0, N, 2):
        if A[i] < A[i + 1]:
            winner[idx] = A[i + 1]  # Winner
            loser[idx] = A[i]  # Loser
        else:
            winner[idx] = A[i]
            loser[idx] = A[i + 1]
        idx += 1

    m = 0

    while idx < N - 1:
        if winner[m] < winner[m + 1]:
            winner[idx] = winner[m + 1]
            loser[idx] = winner[m]
            prior[idx] = m + 1  # Previous winners
        else:
            winner[idx] = winner[m]
            loser[idx] = winner[m + 1]
            prior[idx] = m
        m += 2
        idx += 1

    largest = winner[m]  # First maximum at the root of the tree
    second = loser[m]  # The second maximum is found among the losers
    m = prior[m]

    # Finding the second maximum
    while m >= 0:
        if second < loser[m]:
            second = loser[m]

        m = prior[m]  # Move to the next one if it's larger

    return (largest, second)

print(tournament_two(p))

GitHub link

• Russian version

Турнирное дерево - эффективный поиск максимума в списке - это хороший способ находить максимальный элемент в последовательности чисел. Давайте разберем его более подробно.

Турнирное дерево: Первым шагом является построение турнирного дерева. Это бинарное дерево, в котором каждый узел представляет собой сравнение двух элементов. В каждом узле сохраняется индекс победителя (элемента с наибольшим значением) из двух сравниваемых элементов.

Построение турнирного дерева: Для поиска максимума в последовательности длиной n, вы начинаете с построения турнирного дерева из этих n элементов. Обычно, для этого вы используете структуру данных, которая может быть представлена массивом, где каждый элемент массива соответствует узлу дерева.

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

Количество сравнений: Количество сравнений, необходимых для нахождения максимума, зависит от количества элементов в последовательности. Если n - степень двойки, то потребуется log2(n) сравнений, чтобы найти максимум. Это так потому, что каждое сравнение уменьшает количество оставшихся элементов вдвое.

Например, для n = 8, как в вашем примере, потребуется log2(8) = 3 сравнения, чтобы найти максимум.

Таким образом, турнирное дерево предоставляет эффективный способ поиска максимума, и количество сравнений равно log2(n), где n - длина последовательности.