🔥 Как правильно использовать heapq для поиска K-го наибольшего элемента

Если вы готовитесь к собеседованиям по Python — почти наверняка встретите задачу на Kth Largest. И здесь есть важный нюанс 👇

heapq в Python работает только как min heap

Попытка использовать heapify_max() на большинстве платформ приведёт к ошибке (полноценно появится только в Python 3.14+).

❌ Наивный способ (через отрицания)

Можно «сымитировать» max heap:

import heapq

nums = [3, 2, 1, 5, 6, 4]
max_heap = [-x for x in nums]
heapq.heapify(max_heap)

largest = -max_heap[0]

Подходит для небольших массивов, но плохо масштабируется.
Если данные большие (например, поток из миллиардов чисел) — это неэффективно по памяти.

✅ Как ожидают увидеть на собеседовании

Используйте min heap размера K

Идея:
— вы храните только K самых больших элементов
— минимальный среди них — это и есть ответ

🏆 Представьте это как «топ-10» список:

Решение:

import heapq

def find_kth_largest(nums: list[int], k: int) -> int:
    heap = nums[:k]
    heapq.heapify(heap)

    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)

    return heap[0]

Почему это важно
— Время: O(N log K)
— Память: O(K)
— Подходит для потоковых данных

📍 Навигация: Вакансии • Задачи • Собесы

Библиотека питониста

#буст