Python. Объединить отсортированные списки в один

Предположим, вы решили провести чемпионат мира по оглаживанию собак. Кто погладит больше всех шерстяных волчар за день, тот и победил. Участники не смогли собраться вместе, поэтому каждый город провёл независимое состязание и прислал результат:

washington = [
    (99, "Френк"),
    (80, "Клер"),
    (73, "Зоя")
]

moscow = [
    (90, "Валера"),
    (88, "Мария"),
    (50, "Анатолий")
]

beijing = [
    (123, "Чан"),
    (109, "Пинг"),
    (70,  "Ки"),
]

Теперь ваша задача — выбрать трёх призёров. Я знаю как минимум один простой способ:

all = sorted(washington + moscow + beijing)
winners = all[-3:]

>>> winners
[(99, 'Френк'), (109, 'Пинг'), (123, 'Чан')]

Если всего n участников, такая реализация займёт 2n памяти и потребует O(n log n) операций. Довольно расточительно.

Можно сделать то же самое за константное время и память:

import heapq

all = heapq.merge(washington, moscow, beijing, reverse=True)

>>> next(all)
(123, 'Чан')

>>> next(all)
(109, 'Пинг')

>>> next(all)
(99, 'Френк')

heapq.merge() возвращает генератор, который работает поверх исходных коллекций — поэтому не расходует лишнюю память. И он учитывает, что исходные списки уже отсортированы — поэтому не выполняет лишних действий.

P.S. Френк, всего лишь третье место. Не ожидал от тебя.