0Pricing
DSA Interview Prep · Leçon

heapq de Python et astuces pour les tas max

Utilisez heapq.heappush/heappop, inversez les valeurs pour simuler un tas max et appliquez heapq.nlargest/nsmallest aux recherches rapides des k meilleurs éléments.

heapq de Python et astuces pour les tas max est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.

Présentation du module heapq de Python

Le module heapq de Python fournit un tas min implémenté au-dessus d’une liste Python ordinaire. Contrairement à une classe de tas dédiée, heapq agit directement sur des listes existantes, sur place. Les fonctions du module sont : heapify pour construire un tas en O(n), heappush pour ajouter un élément en O(log n), heappop pour supprimer le minimum en O(log n), ainsi que heappushpop / heapreplace pour gagner en efficacité en combinant ces opérations.

import heapq

# heapq operates on plain Python lists
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)

print('Heap array:', heap)          # internal array (not sorted!)
print('Peek min:', heap[0])         # O(1) min access
print('Pop min:', heapq.heappop(heap))  # 1
print('Next min:', heap[0])         # 2

# heapify: turn any list into a heap in O(n)
data = [9, 4, 7, 1, 3, 6, 2]
heapq.heapify(data)
print('Heapified:', data, '| min:', data[0])

Tas max en inversant les valeurs

Python ne fournit avec heapq qu’un tas min. Pour simuler un tas max, prenez l’opposé de toutes les valeurs avant de les insérer, puis prenez à nouveau leur opposé lors de l’extraction. Cela fonctionne parce que le tas trie selon les valeurs stockées, et que l’inversion des signes inverse l’ordre. N’oubliez jamais d’inverser des deux côtés : avant l’insertion et après l’extraction. Oublier l’une de ces étapes est une erreur fréquente en entretien.

import heapq

max_heap = []
for val in [5, 1, 8, 3, 9, 2]:
    heapq.heappush(max_heap, -val)  # negate on push

print('Max-heap internal:', max_heap)  # all negated

# Pop in descending order:
results = []
while max_heap:
    results.append(-heapq.heappop(max_heap))  # negate on pop
print('Sorted descending:', results)  # [9, 8, 5, 3, 2, 1]

# Common pattern: top-k largest
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
k = 3
heap = []
for x in data:
    heapq.heappush(heap, -x)
print('Top', k, ':', [-heapq.heappop(heap) for _ in range(k)])

heapq.nlargest et nsmallest

heapq.nlargest(k, iterable) et heapq.nsmallest(k, iterable) renvoient les k éléments les plus grands ou les plus petits. Leur complexité est en O(n log k), ce qui est plus efficace qu’un tri complet en O(n log n) lorsque k est beaucoup plus petit que n. En interne, ils utilisent un tas de taille k. Lorsque k est proche de n, Python revient à un tri complet. Utilisez-les pour obtenir ponctuellement les k meilleurs éléments sans conserver un tas permanent.

import heapq

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

# Top 3 largest:
print(heapq.nlargest(3, data))   # [9, 8, 7]
# Top 3 smallest:
print(heapq.nsmallest(3, data))  # [1, 1, 2]

# With a key function:
words = ['banana', 'apple', 'cherry', 'date', 'elderberry']
print(heapq.nlargest(2, words, key=len))   # ['elderberry', 'banana']
print(heapq.nsmallest(2, words, key=len))  # ['date', 'apple']

# Note: when k ~ n, use sorted() instead:
# sorted(data)[-k:]  or  sorted(data, reverse=True)[:k]

Tas avec des tuples pour des clés complexes

Lorsque les éléments du tas nécessitent une clé de comparaison personnalisée, stockez-les sous forme de tuples (priority, data). Python compare les tuples élément par élément avec heapq, et compare donc d’abord les priorités. Si les priorités sont égales, il compare le deuxième élément — cela peut provoquer des erreurs si les données ne sont pas comparables. Le modèle le plus sûr consiste à inclure un compteur unique comme critère de départage, afin d’éviter de comparer directement les éléments de données.

import heapq
import itertools

# Pattern: (priority, counter, item)
# Counter ensures unique tiebreaker, avoids comparing items
counter = itertools.count()
heap = []

def push_task(priority, task):
    heapq.heappush(heap, (priority, next(counter), task))

push_task(3, 'low priority task')
push_task(1, 'high priority task')
push_task(2, 'medium priority task')
push_task(1, 'another high priority')

while heap:
    pri, cnt, task = heapq.heappop(heap)
    print(f'P{pri}: {task}')
# Output in priority order: P1, P1, P2, P3

heapq.merge : fusion d’itérables triés

heapq.merge(*iterables) fusionne paresseusement plusieurs itérables triés en une sortie triée unique sans charger toutes les données en mémoire. Cela équivaut à une fusion à k voies utilisant un tas min de taille k et est utilisé dans les algorithmes de tri externe. La fonction renvoie un itérateur, donc les éléments sont produits un par un — ce qui est idéal pour les grands ensembles de données ou les scénarios de flux.

import heapq

# Merge multiple sorted lists efficiently
sorted_lists = [
    [1, 5, 9],
    [2, 6, 8],
    [3, 4, 7]
]

# heapq.merge takes sorted iterables and returns a merged sorted iterator
merged = list(heapq.merge(*sorted_lists))
print('Merged:', merged)  # [1, 2, 3, 4, 5, 6, 7, 8, 9]

# The k-way merge manually (educational version):
def merge_k_sorted(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    result = []
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        if elem_idx + 1 < len(lists[list_idx]):
            heapq.heappush(heap, (lists[list_idx][elem_idx+1], list_idx, elem_idx+1))
    return result

print('Manual k-way:', merge_k_sorted(sorted_lists))

Schéma de suppression différée pour les tas

Lorsque vous devez supprimer des éléments quelconques d’un tas sans connaître leur indice, utilisez la suppression différée : marquez les éléments comme supprimés dans un ensemble séparé, puis ignorez-les lors de l’extraction. Cette approche est en O(log n) amorti et évite la complexité liée au suivi des indices. Il s’agit de l’approche standard dans l’algorithme de Dijkstra avec des entrées en double et les simulations d’ordonnanceurs de tâches.

import heapq

class LazyHeap:
    def __init__(self):
        self._heap = []
        self._removed = set()

    def push(self, task):
        heapq.heappush(self._heap, task)

    def remove(self, task):
        self._removed.add(task)  # mark as removed

    def pop(self):
        while self._heap:
            task = heapq.heappop(self._heap)
            if task not in self._removed:
                return task
        return None

lh = LazyHeap()
for t in [5, 1, 8, 3, 2]:
    lh.push(t)
lh.remove(1)  # 'delete' 1 lazily
lh.remove(8)  # 'delete' 8 lazily
results = [lh.pop() for _ in range(3)]
print(results)  # [2, 3, 5] -- 1 and 8 skipped

K-ième plus grand élément dans un flux

K-ième plus grand élément dans un flux (LeetCode #703) maintient un tas min de taille k. La racine du tas contient toujours le k-ième plus grand élément rencontré jusqu’à présent. Lorsqu’un nouveau nombre arrive : insérez-le et, si le tas dépasse la taille k, retirez le minimum. La racine est toujours le k-ième plus grand élément, car exactement k-1 éléments du tas sont plus grands qu’elle.

import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.heap = []
        for num in nums:
            self.add(num)

    def add(self, val):
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)  # remove smallest
        return self.heap[0]  # kth largest = root of min-heap

# k=3, initial=[4,5,8,2]
kl = KthLargest(3, [4, 5, 8, 2])
print(kl.add(3))   # 4 (top 3: 8,5,4 -- kth=4)
print(kl.add(5))   # 5 (top 3: 8,5,5 -- kth=5)
print(kl.add(10))  # 5 (top 3: 10,8,5 -- kth=5)
print(kl.add(9))   # 8 (top 3: 10,9,8 -- kth=8)

Trouver k paires de somme minimale

Trouver k paires de somme minimale (LeetCode #373) utilise un tas min pour générer les paires dans l’ordre. Commencez avec toutes les paires (nums1[0], nums2[j]) pour chaque j. Retirez le minimum puis, pour la paire extraite (nums1[i], nums2[j]), insérez (nums1[i+1], nums2[j]) — la candidate suivante de la même colonne. Il s’agit d’un schéma courant pour générer des paires ou des produits ordonnés à l’aide d’un tas.

import heapq

def k_smallest_pairs(nums1, nums2, k):
    if not nums1 or not nums2:
        return []
    heap = []
    # Initialize with pairs (nums1[0], nums2[j])
    for j in range(min(k, len(nums2))):
        heapq.heappush(heap, (nums1[0] + nums2[j], 0, j))
    result = []
    while heap and len(result) < k:
        total, i, j = heapq.heappop(heap)
        result.append([nums1[i], nums2[j]])
        if i + 1 < len(nums1):
            heapq.heappush(heap, (nums1[i+1] + nums2[j], i+1, j))
    return result

print(k_smallest_pairs([1,7,11], [2,4,6], 3))
# [[1,2], [1,4], [1,6]]

Ordonnanceur de tâches avec un tas max

Ordonnanceur de tâches (LeetCode #621) demande de calculer le temps minimal nécessaire pour planifier n tâches, avec une période de refroidissement de n intervalles entre deux occurrences d’une même tâche. Utilisez un tas max contenant les fréquences des tâches : à chaque instant, choisissez la tâche disponible la plus fréquente, diminuez son compteur et placez-la en période de refroidissement. Traitez k=n+1 tâches par cycle, ou complétez avec du temps d’inactivité. Cette approche gloutonne avec un tas max fournit la solution optimale.

import heapq
from collections import Counter

def least_interval(tasks, n):
    freq = Counter(tasks)
    heap = [-f for f in freq.values()]  # max-heap (negated)
    heapq.heapify(heap)
    time = 0
    while heap:
        cycle = n + 1
        temp = []
        for _ in range(cycle):
            if heap:
                temp.append(heapq.heappop(heap))
        for f in temp:
            if f + 1 < 0:  # still tasks remaining
                heapq.heappush(heap, f + 1)
        # Add full cycle or remaining tasks if queue empty
        time += cycle if heap else len(temp)
    return time

print(least_interval(['A','A','A','B','B','B'], 2))  # 8
print(least_interval(['A','A','A','B','B','B'], 0))  # 6

Tas dans l’algorithme de Dijkstra

La file de priorité de l’algorithme de Dijkstra est implémentée avec un tas min. Stockez les tuples (distance, node) et traitez toujours en premier le nœud non visité le plus proche. Lorsque vous extrayez un nœud dont la distance est supérieure à la plus courte distance actuellement connue, ignorez-le : il s’agit d’une entrée obsolète issue de la suppression différée. Cela évite d’avoir recours à une opération de diminution de clé et conserve une implémentation simple, tout en maintenant une complexité de O((V + E) log V).

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]  # (distance, node)
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:   # stale entry, skip
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

graph = {
    'A': [('B', 4), ('C', 1)],
    'B': [('D', 1)],
    'C': [('B', 2), ('D', 5)],
    'D': []
}
print(dijkstra(graph, 'A'))  # {'A':0,'B':3,'C':1,'D':4}

Réorganiser une chaîne avec un tas max

Réorganiser une chaîne (LeetCode #767) demande de réarranger une chaîne afin qu’aucun caractère adjacent ne soit identique. Utilisez un tas max de (-frequency, char). À chaque étape, extrayez le caractère le plus fréquent. Si le caractère précédent est identique au caractère le plus fréquent, extrayez plutôt le deuxième caractère le plus fréquent. Cette approche gloutonne garantit que le caractère le plus contraint est placé le plus tôt possible.

import heapq
from collections import Counter

def reorganize_string(s):
    freq = Counter(s)
    heap = [(-f, c) for c, f in freq.items()]
    heapq.heapify(heap)
    result = []
    prev_freq, prev_char = 0, ''
    while heap:
        freq, char = heapq.heappop(heap)
        result.append(char)
        # Push back the previous character if still remaining
        if prev_freq < 0:
            heapq.heappush(heap, (prev_freq, prev_char))
        prev_freq, prev_char = freq + 1, char  # decrement freq (less negative)
    result_str = ''.join(result)
    # Verify no adjacent duplicates
    return result_str if len(result_str) == len(s) else ''

print(reorganize_string('aab'))   # 'aba'
print(reorganize_string('aaab'))  # '' (impossible)

Vérification rapide

Testez votre compréhension des concepts de Structures de données et algorithmes — Préparation aux entretiens de programmation présentés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris l’interface de programmation du module heapq de Python, notamment heapify, heappush, heappop, nlargest, nsmallest et merge, la simulation d’un tas max en inversant les valeurs, ainsi que les schémas courants sur les tas rencontrés en entretien, notamment les k meilleurs éléments en flux, le k-ième plus grand élément dans un flux, l’ordonnanceur de tâches et Dijkstra. Ensuite, nous étudierons la médiane d’un flux de données et la fusion à k voies.

Questions Fréquemment Posées

La leçon « heapq de Python et astuces pour les tas max » est-elle gratuite ?

Oui — le texte complet de « heapq de Python et astuces pour les tas max » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « heapq de Python et astuces pour les tas max » ?

Utilisez heapq.heappush/heappop, inversez les valeurs pour simuler un tas max et appliquez heapq.nlargest/nsmallest aux recherches rapides des k meilleurs éléments. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?

Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.

Combien de temps prend la leçon « heapq de Python et astuces pour les tas max » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?

Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Propriété des tas et représentation par tableau
  2. Heapify, push et pop depuis zéro
  3. heapq de Python et astuces pour les tas max
  4. Médiane d’un flux de données et fusion k-voies
← Retour à DSA Interview Prep