Heapq.nsmallest: примеры (PYTHON)

Использование heapq.nsmallest для поиска минимальных элементов
Раздел: Очереди с приоритетом, Алгоритмы
heapq.nsmallest(n, iterable, key): list
типовые примерыheapq.nsmallest на php, c#, sql, javaheapq.nsmallest изменения pythonпримеры расширенные

Описание функции heapq.nsmallest

Функция heapq.nsmallest(n, iterable, key=None) является частью модуля heapq в Python и предназначена для эффективного поиска n наименьших элементов из итерируемого объекта. Она полезна при работе с большими наборами данных, когда требуется найти несколько минимальных значений без полной сортировки последовательности.

Аргументы функции:

  • n (целое число): количество наименьших элементов для возврата. Если n больше размера итерируемого объекта, функция вернет все элементы в отсортированном порядке.
  • iterable: итерируемый объект (список, кортеж, генератор), из которого производится выборка элементов.
  • key (опционально): функция, принимающая один аргумент и возвращающая ключ для сравнения элементов. Работает аналогично параметру key в функции sorted().

Возвращаемое значение: список из n наименьших элементов, отсортированных по возрастанию. Алгоритм эффективен для небольших значений n, так как использует двоичную кучу.

Примеры использования

Пример с простым списком чисел:

import heapq
numbers = [10, 2, 45, 1, 9, 7]
result = heapq.nsmallest(3, numbers)
print(result)
[1, 2, 7]

Пример с использованием параметра key:

words = ["яблоко", "апельсин", "банан", "виноград"]
result = heapq.nsmallest(2, words, key=len)
print(result)
['банан', 'яблоко']

Пример с итерируемым объектом и n, превышающим размер данных:

data = (5, 3, 8)
result = heapq.nsmallest(5, data)
print(result)
[3, 5, 8]

Похожие функции в Python

sorted(iterable)[:n]: полная сортировка с последующим срезом. Эффективна для относительно небольших коллекций или когда n близко к размеру данных. Для больших данных и малых n heapq.nsmallest работает быстрее.

min(iterable): находит один минимальный элемент. Используется, когда требуется только наименьшее значение.

heapq.heappush() + heapq.heappop(): ручное управление кучей предоставляет больше контроля, но требует написания дополнительного кода. heapq.nsmallest инкапсулирует эту логику.

Аналоги в других языках программирования

JavaScript: нет прямой встроенной функции. Обычно используют сортировку или бибилиотеки. Пример с сортировкой:

let numbers = [10, 2, 45, 1, 9, 7];
let result = numbers.sort((a, b) => a - b).slice(0, 3);
console.log(result); // [1, 2, 7]

Java: использование PriorityQueue или стримов.

import java.util.List;
import java.util.stream.Collectors;
List numbers = List.of(10, 2, 45, 1, 9, 7);
List result = numbers.stream()
    .sorted()
    .limit(3)
    .collect(Collectors.toList());
// result = [1, 2, 7]

SQL: запрос с ORDER BY и LIMIT.

SELECT column FROM table ORDER BY column ASC LIMIT 3;

Go: сортировка с использованием пакета sort.

package main
import (
    "fmt"
    "sort"
)
func main() {
    nums := []int{10, 2, 45, 1, 9, 7}
    sort.Ints(nums)
    result := nums[:3]
    fmt.Println(result) // [1 2 7]
}

Типичные ошибки

Передача неитерируемого объекта:

import heapq
result = heapq.nsmallest(2, 123)  # Ошибка: int не итерируем
TypeError: 'int' object is not iterable

Использование несуществующего ключа в словарях без обработки:

import heapq
data = [{"x": 5}, {"y": 3}]
result = heapq.nsmallest(1, data, key=lambda d: d["x"])  # Ключ "x" отсутствует во втором элементе
KeyError: 'x'

Ожидание модификации исходного итерируемого объекта:

import heapq
lst = [5, 1, 9]
heapq.nsmallest(2, lst)
print(lst)  # Список остается неизменным
[5, 1, 9]

Изменения в последних версиях

Функция heapq.nsmallest остается стабильной, без значительных изменений в поведении или аргументах в последних основных версиях Python (3.x). Основные оптимизации алгоритма были завершены в более ранних релизах. Документация рекомендует использовать функцию для поиска относительно небольшого количества элементов, так как при больших значениях n эффективность может снижаться.

Расширенные примеры

Работа с объектами пользовательских классов:

Пример python
import heapq
class Product:
    def __init__(self, name, price):
        self.name = name
        self.price = price
    def __repr__(self):
        return f"{self.name}: {self.price}"
products = [
    Product("Молоко", 80),
    Product("Хлеб", 50),
    Product("Сыр", 300),
    Product("Вода", 40)
]
cheapest = heapq.nsmallest(2, products, key=lambda p: p.price)
print(cheapest)
[Вода: 40, Хлеб: 50]

Использование с генератором для обработки больших потоков данных:

Пример python
import heapq
import random
def generate_numbers():
    for _ in range(100000):
        yield random.randint(1, 1000000)
smallest = heapq.nsmallest(5, generate_numbers())
print(f"5 наименьших: {smallest}")
5 наименьших: [12, 45, 78, 123, 256]  # примерные значения

Поиск минимальных значений по составному ключу:

Пример python
import heapq
data = [
    ("Иван", 25, 50000),
    ("Мария", 30, 45000),
    ("Петр", 22, 48000),
    ("Ольга", 28, 52000)
]
# Найти двух самых молодых сотрудников
result = heapq.nsmallest(2, data, key=lambda x: x[1])
print(result)
[('Петр', 22, 48000), ('Иван', 25, 50000)]

Эмуляция работы nsmallest с использованием кучи вручную:

Пример python
import heapq
data = [10, 5, 20, 1, 8]
heap = []
for item in data:
    heapq.heappush(heap, item)
result = [heapq.heappop(heap) for _ in range(2)]
print(f"Два наименьших элемента: {result}")
Два наименьших элемента: [1, 5]

питон heapq.nsmallest function comments

En
Heapq.nsmallest Return n smallest elements