Python. Выбрать топ-k элементов списка

Сегодня новое соревнование — граждане города выбирают самое наглое животное. Результаты опроса поступили в виде неупорядоченного списка пар «количество голосов — участник»:

contenders = [
  (31, "индюк"),
  (22, "крыса"),
  (79, "кот"),
  (98, "голубь"),
  (13, "собака"),
  (95, "енот"),
  (15, "хомяк"),
]

Осталось, как обычно, выбрать трёх победителей. Как насчёт такого:

>>> sorted(contenders)[-3:]
[(79, 'кот'), (95, 'енот'), (98, 'голубь')]

Неплохо. Но, как вы помните, сортировка списка занимает O(n log n) операций. Жирновато, чтобы просто выбрать топ-3 элемента.

Вот альтернатива:

>>> import heapq
>>> heapq.nlargest(3, contenders)
[(98, 'голубь'), (95, 'енот'), (79, 'кот')]

Такой вариант использует только O(n) операций — при небольшом k (в данном случае k = 3). Для больших k вариант с sorted() эффективнее.

Ну а если k = 1 (выбираем одного победителя), то так:

>>> max(contenders)
(98, 'голубь')

Я даже знаю, как его зовут ツ