Пример 1.6. Поиск двух наибольших значений A с помощью турнирного дерева

def tournament_two(A):

N = len(A)

winner = [None] * (N-1) ❶

loser = [None] * (N-1)

prior = [-1] * (N-1) ❷

idx = 0

for i in range(0, N, 2): ❸

if A[i] < A[i+1]:

winner[idx] = A[i+1]

loser[idx] = A[i]

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

else:

winner[idx] = winner[m]

loser[idx] = winner[m+1]

prior[idx] = m

m += 2 ❻

idx += 1

largest = winner[m]

second = loser[m] ❼

m = prior[m]

while m >= 0:

if second < loser[m]: ❽

second = loser[m]

m = prior[m]

return (largest, second)

❶ В этих списках мы станем хранить индексы победителей и проигравших в игре, которых будет N – 1.

❷ Когда значение в позиции m проходит на очередной тур, в prior[m] записывается позиция этого значения в предыдущем туре. Для первого тура такой информации нет, поэтому в начале этого списка хранится -1.

❸ Первый тур состоит из N / 2 игр, то есть требует N / 2 сравнений на «меньше» в парах «победитель — проигравший».

❹ Игры победителей во всех следующих турах с записью позиции выигравшего в каждой игре.

❺ Еще N / 2 – 1 сравнение.

❻ Увеличим m на 2 — это игра двух следующих победителей. Когда idx достигнет N – 1, в winner[m] окажется наибольшее значение.

❼ Первый кандидат на второе место; надо еще проверить остальных проигравших чемпиону, возможно, они больше подходят для второго места.

❽ Не больше log2(N) – 1 дополнительное сравнение на «меньше».