Пример 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 дополнительное сравнение на «меньше».
Кіру не тіркелу пікір қалдыру үшін