Trouver les N plus grands ou plus petits éléments

Vous souhaitez créer une liste des N plus grands ou plus petits éléments d'une collection.

import heapq
from random import sample, seed


seed(1)
nums = sample(list(range(1, 51)), 11)
print(nums)
print(heapq.nlargest(3, nums)) # 42, 37, 32
print(heapq.nsmallest(3, nums)) # 5, 8, 9

Ces deux fonctions acceptent également un paramètre key qui permet de les utiliser avec des structures de données plus complexes. Par exemple :

from collections import namedtuple
import heapq


Employee = namedtuple('Employee', ['name', 'salary', 'seniority'])

employees = [
    Employee('Pierre', 3500, 3),
    Employee('Sophie', 4200, 1),
    Employee('Jean', 3800, 5)
]

# Top 2 des salaires les plus élevés
high_salary = heapq.nlargest(2, employees, key=lambda e: e.salary)
print(high_salary)
# [Employé(name='Sophie', salary=4200, seniority=1),
#  Employé(name='Jean', salary=3800, seniority=5)]

# 1er en ancienneté
seniorityer = heapq.nlargest(1, employees, key=lambda e: e.seniority)
print(seniorityer)
# [Employee(name='Jean', salary=3800, seniority=5)]

Si vous recherchez les N plus petits ou plus grands éléments d'une collection et que N est petit par rapport à la taille totale de cette collection, ces fonctions offrent des performances supérieures. En arrière-plan, ces fonctions fonctionnent en convertissant d'abord les données en une liste où les éléments sont ordonnés en tas (heap). Par exemple :

import heapq


data = [3, 1, 4, 1, 5, 9, 2, 6]

# Étape 1 : Conversion en heap (sur place)
heapq.heapify(data)  
# → data devient [1, 1, 2, 3, 5, 9, 4, 6] 
# (structure arborescente implicite)

# Étape 2 : Extraction des 3 plus petits
petits = [heapq.heappop(data) for _ in range(3)]
# → [1, 1, 2]
"""
visualisation
       1
     /   \
    1     2
   / \   / \
  3   5 9   4
 /
6
"""

La caractéristique principale d'un tas (heap) est que heap[0] est toujours l'élément le plus petit. De plus, les éléments suivants peuvent être facilement obtenus en utilisant la méthode heapq.heappop(), qui retire le premier élément et le remplace par le prochain élément le plus petit (une opération qui s'effectue en O(log N), où N est la taille du tas). Par exemple, pour trouver les trois plus petits éléments, vous pourriez faire ceci :

import heapq

data = [5, 3, 8, 1, 4]
heapq.heapify(data)  # Transforme en tas: [1, 3, 8, 5, 4]

# Extraction des 3 plus petits éléments
first = heapq.heappop(data)  # 1, nouveau tas: [3, 4, 8, 5]
second = heapq.heappop(data)   # 3, nouveau tas: [4, 5, 8]
third = heapq.heappop(data) # 4, nouveau tas: [5, 8]

Les fonctions nlargest() et nsmallest() sont particulièrement adaptées lorsque vous cherchez un petit nombre d'éléments. Si vous ne recherchez que le plus petit ou le plus grand élément (N=1), il est plus efficace d'utiliser min() et max(). De même, si N est proche de la taille totale de la collection, il est généralement plus rapide de trier d'abord la liste puis d'utiliser un découpage (par exemple, sorted(items)[:N] ou sorted(items)[-N:]).

Bien qu'il ne soit pas indispensable d'utiliser cette approche, l'implémentation d'un tas (heap) reste un sujet d'étude intéressant et formateur. On en trouve généralement des explications dans les ouvrages classiques d'algorithmique et de structures de données. La documentation officielle du module heapq aborde également ces détails d'implémentation sous-jacents.

Publié le

me contacter

* champ obligatoire