Fiches › Carte › Partie 09 · Coding › coding 07

Heap — le minimum est le seuil d'entrée

On demande k éléments extrêmes — les plus grands, les plus fréquents, les plus proches — et pas l'ordre complet. Trier, c'est répondre à une question qu'on n'a pas posée. Le pattern tient en une phrase : un min-heap de taille k, dont le minimum h[0] est le seuil d'entrée — un nouvel élément n'entre que s'il le dépasse, et il prend la place du minimum. Fil rouge : arr = [5, 1, 9, 3, 7, 8], k = 3, réponse {7, 8, 9} et 3e plus grand = 7 ; le tour qui compte est le quatrième, où 3 > 1 fait sortir le 1. Coût O(n log k) contre O(n log n) — et quand les clés sont bornées, un bucket supprime le log tout entier. Jamais la solution complète : le squelette, la trace, les phrases.

Ce que cette sheet suppose acquis
  • Le rituel TAP. Invariant, variant, conclusion, complexité — c00, pas 1. La boucle est ici la plus simple de toute la série : un balayage de arr, un tour par élément, jamais de retour en arrière.
  • Invariant = conteneur + tranche + « exactement ». c00, pas 2. Le conteneur est le tas, la tranche est arr[0:i+1], et le mot exactement est celui qui fait tout le travail — pas 3.
  • Variant = entier ≥ 0 strictement décroissant. c00, pas 3. Ce n'est pas la taille du tas, qui monte jusqu'à k puis ne bouge plus : c'est n − i, le nombre d'éléments non encore vus.
  • Complexité composée. c00, pas 5. O(n log k) est un produit : n tours, chacun au pire en log k. Le pas 4 montre que le pire cas n'arrive presque jamais.
  • Un tas, c'est un tableau. Aucun pointeur, aucun nœud : l'élément i a ses fils en 2i+1 et 2i+2, et la racine est la case 0. C'est tout ce qu'il faut savoir de la structure — cette sheet parle de ce qu'on en fait, pas de son implémentation.
Hypothèses posées
H1k ≪ n, et k est donné avant de commencer. Tout l'intérêt vient de ce rapport : à k = n le tas fait exactement le travail d'un tri, en plus lent. Le pas 1 en fait un contre-signal explicite. H2Les éléments sont comparables deux à deux par la clé qui décide. Une clé composite se range dans un tuple, et l'ordre du tuple est lexicographique — ce qui est exactement le piège du pas 7. H3heapq est un min-heap, et il n'existe pas de variante max en Python. Tout « max-heap » de cette sheet est un min-heap sur −x ou sur (−clé, …). H4On ne demande pas les k plus grands triés. Le tas les contient sans les ordonner ; si l'ordre compte, c'est un sorted(h) final en O(k log k), qui se dit à voix haute au lieu d'être oublié. H5On énonce le squelette et les phrases. Le corps se remplit devant l'interlocuteur : une sheet de coding ne contient jamais la solution complète.

La chaîne

Le signal, et les deux contre-signaux tronc

Un superlatif partiel : « les k plus grands », « les k plus fréquents », « les k plus proches », « le k-ième plus grand ». Et ses cousins : fusionner k flux triés, servir par ordre de priorité. Dans tous les cas n est grand et k est petit.

on demande k extrêmes, pas l'ordre  ⇒  un tas de taille k

Deux contre-signaux, et ils sont symétriques. k ≈ n : il n'y a plus rien à jeter, on trie — le tas ne fait qu'ajouter une constante. Clés bornées dans [0, m] avec m = O(n) : on n'a plus besoin de comparer du tout, un tableau de listes suffit — pas 6.

« On me demande k éléments extrêmes et pas l'ordre des n, donc trier répondrait à une question que personne n'a posée, donc il me suffit de retenir les k meilleurs vus jusqu'ici, donc le pattern est un tas de taille k et non un tri. »

Application — le fil rouge, et l'ordre de grandeur qui justifie tout

Le fil rouge. arr = [5, 1, 9, 3, 7, 8], k = 3. Les trois plus grands sont {7, 8, 9}, et le 3e plus grand — le k-ième — est 7. Six valeurs : c'est assez court pour se tracer à la main au tableau, et assez long pour que trois évictions différentes s'y produisent.

Pourquoi le rapport k/n décide de tout. Mesuré sur n = 106 valeurs aléatoires : avec k = 10, 999 880 d'entre elles — 99,988 % — sont rejetées par une seule comparaison contre h[0], et seuls 134 remplacements ont lieu. Avec k = 1000 : 99,21 % de rejets, 6 954 remplacements. Le tas n'est presque jamais touché ; c'est un filtre, et le log ne se paie que sur ce qui passe.

Le contre-signal k ≈ n, chiffré. À n = 106, k = 10 : la boucle du tas met 0,022 s, le tri complet 0,147 s — 6,7× plus. À k = n, les deux font le même travail et le tas le fait moins bien : on annonce sorted() et on passe à autre chose.

Ce que la sheet n'aborde pas. L'implémentation du tas (percolation, siftup), les tas de Fibonacci, les files de priorité à clés modifiables. On les nomme si la question tombe ; ici, le tas est une boîte noire à trois opérations.

Le pattern : h[0] est le seuil d'entrée tronc

Pour les k plus grands, un min-heap — l'inverse du réflexe. Sa racine h[0] est le plus petit des k retenus, c'est-à-dire exactement le ticket d'entrée : tout ce qui ne le dépasse pas est jeté en O(1).

v > h[0]  ⇒  heapreplace(h, v)  ·  sinon rien

Remplacer, pas pousser-puis-retirer : heapreplace est une seule percolation, heappush suivi de heappop en fait deux et laisse le tas passer par la taille k+1. Pour les k plus petits, on renverse tout : max-heap, donc min-heap sur −x.

« Le tas est un min-heap, donc sa racine est le plus petit des k que je garde, donc c'est la barre à franchir pour entrer, donc un élément qui ne la dépasse pas ne peut être dans aucun top-k futur et se jette sans toucher au tas. »

Application — le squelette, et le croquis du tas
h = [] pour v dans arr : si len(h) < k : heappush(h, v) sinon si v > h[0] : # h[0] = le seuil heapreplace(h, v) retour h # les k plus grands, NON triés

Quatre lignes, et une seule porte l'idée : v > h[0]. Le reste est de la plomberie. Le si len(h) < k est l'amorce — les k premiers entrent sans examen, puisqu'il n'y a pas encore de seuil à franchir.

le tas après le tour 3 — arr[0:3] = 5, 1, 9 159

case 0 = racine = seuil · fils de 0 : cases 1 et 2 · aucune relation entre 5 et 9

Ce que le croquis dit. Le tas n'est pas trié : il garantit seulement que chaque parent est ≤ ses fils. Mesuré sur 2 000 tirages de 40 valeurs avec k = 5 : 86,9 % du temps le tableau sorti n'est pas dans l'ordre croissant. La seule case sur laquelle on peut compter est la 0 — et c'est la seule dont on a besoin.

Le k-ième plus grand, gratuitement. À la sortie, h[0] est la k-ième plus grande valeur. LeetCode 215 ne demande rien d'autre : le même code, et on retourne h[0] au lieu de h.

Figure 1 — la course complète sur le fil rouge

Les six valeurs de arr : le grand chiffre est la valeur, le petit son indice. Cadre vert = l'élément du tour, ambre = les indices actuellement dans le tas, et la ligne inv donne le contenu du tas trié — attention, trié pour être lisible, pas parce que le tas l'est (voir le croquis ci-dessus). Fais « pas › » et arrête-toi à l'image 4 : c'est le premier tour où le tas est plein, h[0] = 1 est le seuil, la valeur du tour vaut 3, et 3 > 1 — donc le 1 sort et le 3 entre. Les images 5 et 6 rejouent la même scène avec 7 > 3 puis 8 > 5, et à chaque fois le seuil monte : 1, puis 3, puis 5, puis 7. Ce seuil qui ne redescend jamais, c'est tout le mécanisme. Bilan : 3 poussées, 3 remplacements, 0 rejet — sur ces six valeurs rangées exprès, rien n'est jeté ; sur 106 valeurs aléatoires, 99,988 % le sont.

L'invariant, le variant, la conclusion tronc

L'invariant se récite sur la tranche déjà lue, et le mot qui porte tout est exactement :

après le tour i : h = les min(k, i+1) plus grandes valeurs de arr[0:i+1]  ·  h[0] = la plus petite d'entre elles

Variant : n − i, entier ≥ 0 qui décroît d'une unité par tour. Pas la taille du tas, qui croît jusqu'à k puis reste fixe — elle ne prouve rien.

« Le tas contient exactement les k plus grands de la tranche lue, donc une valeur qui ne dépasse pas le plus petit d'entre eux n'est plus grande qu'aucun des k, donc l'ignorer conserve l'invariant, donc à la dernière lecture le tas contient exactement les k plus grands de arr. »

Application — l'invariant récité sur les six tours du fil rouge
  • i = 0, v = 5. Tas non plein → on pousse. h = {5}, seuil 5. Exactement le plus grand de [5]. ✔
  • i = 1, v = 1. Non plein → on pousse. h = {1, 5}, seuil 1. Exactement les 2 plus grands de [5, 1]. ✔
  • i = 2, v = 9. Non plein → on pousse. h = {1, 5, 9}, seuil 1. Le tas est plein : le seuil devient actif.
  • i = 3, v = 3. 3 > 1 → remplacement, le 1 sort. h = {3, 5, 9}, seuil 3. Exactement les 3 plus grands de [5, 1, 9, 3]. ✔
  • i = 4, v = 7. 7 > 3 → le 3 sort. h = {5, 7, 9}, seuil 5.
  • i = 5, v = 8. 8 > 5 → le 5 sort. h = {7, 8, 9}, seuil 7.
  • Conclusion. Variant nul donc la tranche vaut arr tout entier donc h = {7, 8, 9} est exactement le top-3, et h[0] = 7 est le 3e plus grand.

Le seuil est monotone, et c'est ce qui rend l'argument court. 5 → 1 → 1 → 3 → 5 → 7 : dès que le tas est plein il ne peut que monter, puisqu'on ne remplace que par plus grand. Un élément rejeté à l'instant i l'aurait donc été à tous les instants suivants : rien n'est perdu.

Vérifié à l'exécution. La boucle confrontée à sorted(arr)[-k:] sur des tirages aléatoires, n = 106 et k ∈ {10, 100, 1000} : 0 désaccord.

Le coût : un produit, et une borne très lâche

n tours, et chaque tour touche un tas de taille k : une percolation coûte au pire log k. Le tas ne grandit jamais au-delà de k, donc le log est en k et non en n.

temps O(n log k)  ·  espace O(k)  —  contre O(n log n) et O(n) pour le tri

Trois choses à nommer sans les dérouler. Quickselect : O(n) en moyenne, O(n2) au pire, et il faut tout le tableau en mémoire. heapify : O(n), pas O(n log n). Le tas de taille k, lui, est le seul des trois qui tourne sur un flux.

« Je fais un tour par élément et chaque tour ne touche qu'un tas de taille k, donc le coût d'un tour est log k et non log n, donc le total est n log k, donc le gain sur le tri est le rapport log n sur log k — un facteur six à un million d'éléments, pas un ordre de grandeur. »

Application — comparaisons comptées, pas estimées

Ce que la borne annonce. n = 20 000, k = 10 : n log₂ k = 66 439 comparaisons au pire.

Ce qui se passe vraiment (comparaisons instrumentées) : 20 329 au total, soit 30,6 % de la borne. Et la décomposition est l'idée du pas 2, chiffrée :

  • 19 990 comparaisons sont le seul test de seuil v > h[0] — une par élément, en O(1) ;
  • 84 remplacements seulement franchissent la barre ;
  • 339 comparaisons se passent à l'intérieur du tas, soit ≈ 84 × log₂ 10. C'est le seul endroit où le log existe.

Les trois concurrents, même n, même k. Min-heap de tous les n puis heappop n−k fois : 293 204 comparaisons (14×). Max-heap de tous les n puis k retraits : 33 177 (1,6×, mais O(n) d'espace — pas 7). Tri complet : 260 347.

Chronométré, n = 106, k = 10. Tas de taille k 0,022 s · max-heap des n 0,053 s · tri 0,147 s · min-heap des n drainé 0,628 s. Même réponse dans les quatre cas.

Figure 2 — n log k, n log n et n, en échelles log

Les deux axes sont logarithmiques : chaque graduation multiplie par 10. Trois droites, donc trois puissances de n — et elles sont parallèles, ce qui est exactement le message. Bouge k et regarde la ligne bleue : elle glisse verticalement entre la ligne ambre (n, le plancher : lire l'entrée) et la violette (n log n, le tri), sans jamais changer de pente. Ce que ça veut dire : le tas ne change pas la classe de complexité, il divise une constante — à n = 106 et k = 10, le gain sur le tri est 6×, pas mille. Pousse k jusqu'à ce que les readouts virent au rouge : au-delà de k = n la ligne bleue passe au-dessus de la violette et le tas coûte plus cher que le tri — c'est le contre-signal du pas 1, vu de face. Et la ligne ambre reste toujours en dessous : le seul moyen de la toucher, c'est d'arrêter de comparer — pas 6.

Les variantes : même tas, autre clé

La charpente ne bouge pas ; seule change la clé qu'on met dedans. k plus fréquents (LC 347) : compter dans un dict, puis top-k sur la paire (fréquence, valeur). k plus proches de l'origine : max-heap sur d2 — on ne prend jamais la racine, elle ne change pas l'ordre.

fusion de k listes triées : tas des k têtes (valeur, i_liste, j)  ⇒  O(N log k)

La fusion est le cas où le tas a une autre taille que la réponse : k est le nombre de flux, pas le nombre de résultats. On sort N valeurs au total, et chaque sortie ne coûte qu'une percolation d'un tas à k éléments.

« La structure ne sait rien du problème, elle ne sait comparer que des clés, donc changer de problème revient à changer de clé et rien d'autre, donc les k plus fréquents, les k plus proches et la fusion de k flux sont le même code avec trois tuples différents. »

Application — la fusion, déroulée sur des chiffres

Cinq listes triées de six valeurs, soit N = 30 et k = 5 :

[23, 33, 37, 83, 87, 87] [18, 28, 29, 82, 85, 93] [ 9, 16, 23, 27, 68, 95] [ 3, 16, 37, 55, 77, 87] [ 1, 10, 18, 33, 35, 57]

Le tas ne contient jamais que 5 éléments — les têtes courantes : au départ (23,0) (18,1) (9,2) (3,3) (1,4). On retire la plus petite, on sort 1, et on repousse la suivante de la liste 4. Trente retraits plus tard, la fusion est identique à sorted() des 30 valeurs — vérifié. Coût : 30 × log₂ 5, contre 30 × log₂ 30 pour un tri naïf de la concaténation.

Le j dans le tuple. (valeur, i_liste, j) : i dit dans quelle liste repêcher, j dit où. Sans eux, on sait quelle valeur sortir mais pas quoi pousser à sa place — et le tuple à trois champs règle en prime le problème d'égalité du pas 7.

Les k plus proches, et le piège du signe. On veut les plus petites distances, donc un max-heap, donc un min-heap sur −d2. Le seuil est alors le plus mauvais des k retenus — même phrase, autre bout.

Quand on arrête de comparer : le bucket

Le log de n log k vient d'une seule chose : on compare. Si les clés sont des entiers dans [0, m] avec m = O(n), on peut s'en passer — la clé est un indice.

tableau de listes, indice = clé  ;  lire depuis le haut  ⇒  O(n), zéro comparaison

Le cas qui tombe en entretien est LC 347 : une fréquence est un entier de 0 à n, donc bornée par construction. C'est le contre-signal du pas 1 : ce n'est pas que le tas soit lent, c'est que la question a changé de nature.

« Le log vient de ce que je compare des clés entre elles, donc si une clé est un entier borné je peux m'en servir comme d'un indice, donc je range sans comparer et je lis depuis le haut, donc le coût tombe à n — et la borne sur la clé est l'hypothèse à énoncer avant de l'annoncer. »

Application — LC 347 sur six valeurs, puis la nuance mesurée

arr = [1, 1, 1, 2, 2, 3], k = 2. Comptage : {1 : 3, 2 : 2, 3 : 1}. On range chaque valeur dans le seau de sa fréquence :

—321——— f=0f=1f=2f=3f=4f=5f=6

on lit de f = 6 vers f = 1 et on s'arrête à k = 2 → [1, 2]

Le tableau a n+1 seaux et pas un de plus : une fréquence ne peut pas dépasser n. C'est cette borne-là qu'on énonce, et c'est elle qui achète le O(n).

La nuance, mesurée. « O(n) » n'est pas « plus rapide ». Sur n = 106 avec k = 3 : quand il n'y a que 50 valeurs distinctes, le bucket est 100× plus lent que le tas (2,9 ms contre 0,03 ms), parce qu'allouer 106 seaux coûte O(n) alors que le tas ne voit que 50 items. Avec 50 000 puis 600 000 distinctes, le bucket repasse devant — de 1,24×. Asymptotiquement il gagne ; en constante, c'est mince, et le dire vaut mieux que l'annoncer trop fort.

La phrase à dire. « Les fréquences sont bornées par n, donc je peux les utiliser comme indices et descendre en O(n) ; avec le tas je reste en n log k, et sur ce jeu de données ce sera probablement plus rapide. » On donne les deux, on choisit, et on justifie.

Où ça casse casse

Le piège n'est pas le sens du tas, c'est sa taille. « k plus grands ⇒ heap » se transforme en « je mets les n éléments dans un tas », et de là il n'y a plus qu'un pas jusqu'à le vider. Rien n'est levé, la réponse est juste, la facture change d'ordre.

tas de taille k : O(n log k), espace O(k)  →  tas de taille n : espace O(n), et pas de flux

Et le cas vraiment silencieux, celui qui rend la réponse fausse : une clé composite dont on inverse un seul champ. Le tuple se compare champ par champ ; nier la fréquence sans nier le mot est la seule façon de garder le tri secondaire dans le bon sens.

« Un tuple se compare lexicographiquement, donc renverser l'ordre en niant le premier champ renverse aussi l'ordre des suivants, donc l'égalité de fréquence se tranche à l'envers de ce que l'énoncé demande, donc la fonction rend deux mots dans le mauvais ordre sans lever la moindre erreur. »

Les deux contre-exemples, à sortir de mémoire

Le tas de taille n, chiffré. n = 106, k = 10. Min-heap de tous les n puis heappop n−k fois : 0,628 s et 293 204 comparaisons, contre 0,022 s et 20 329 pour le tas de taille k — 29× en temps, 14× en comparaisons. Max-heap de tous les n puis k retraits : 0,053 s, donc rapide — mais O(n) d'espace, et il faut connaître n, donc il ne tourne pas sur un flux. Les trois rendent {les mêmes 10 valeurs} : aucun test ne les distingue.

La clé composite, LC 692 (k mots les plus fréquents, égalité tranchée par l'ordre alphabétique). Sur {pomme : 3, abricot : 3, cerise : 2, datte : 1} avec k = 2 : nlargest sur (f, mot) renvoie ['pomme', 'abricot'] — faux. nsmallest sur (−f, mot) renvoie ['abricot', 'pomme'] — juste. Quatre mots suffisent à le voir, et aucune exception n'est levée dans les deux cas.

Pourquoi c'est indétectable à la main. Il faut une égalité de clé primaire et une clé secondaire qui compte. Sur des flottants tirés au hasard, l'égalité n'arrive jamais : la version fautive passe tous les tests aléatoires. Le contre-exemple doit être construit, pas cherché.

La phrase qui tue. « Le tas doit avoir la taille de la réponse, pas celle de l'entrée — sinon j'ai payé l'espace de l'entrée pour rien, et je ne peux plus lire un flux. »

Pièges Python — quatre lignes qui ont l'air justes
  • heapq est un min-heap, et il n'y a pas d'option. Un max-heap se fabrique en poussant −x, ou des tuples (−clé, valeur). Oublier de re-nier à la sortie rend des valeurs négatives — bruyant, donc bénin. Nier aussi le second champ est silencieux : voir ci-dessus.
  • Tuples à clé égale et charge non comparable. heappush(h, (1, {'a': 1})) puis (1, {'b': 2}) lève TypeError: '<' not supported between instances of 'dict' and 'dict' — vérifié. Le tas compare le second champ uniquement en cas d'égalité du premier, donc le bug est intermittent : il attend une égalité. Remède : un compteur monotone en deuxième position, (clé, i, objet).
  • heapify est O(n), pousser n fois est O(n log n). Mesuré sur 106 flottants : 0,026 s contre 0,052 s, un facteur 2. Le ratio est modeste en CPython parce que heapify et heappush sont tous deux en C — mais la différence de classe est réelle, et c'est elle qu'on énonce.
  • Retourner h en le croyant trié. Il ne l'est pas : 86,9 % des tirages donnent un tableau désordonné (2 000 essais, n = 40, k = 5). Seule la case 0 est garantie. Si l'énoncé demande l'ordre, sorted(h) — O(k log k), négligeable, mais à dire.

Résumé

À retenir
  1. Signal : k extrêmes — plus grands, plus fréquents, plus proches, k-ième — ou k flux à fusionner, avec k ≪ n.
  2. Le pattern : min-heap de taille k pour les k plus grands. h[0] est le seuil d'entrée ; heapreplace, jamais push-puis-pop.
  3. Invariant : h = exactement les k plus grands de arr[0:i+1], et h[0] le plus petit d'entre eux. Variant : n − i, jamais la taille du tas.
  4. Coût : O(n log k), espace O(k). Borne lâche : 99,99 % des éléments sont rejetés par une comparaison. Gain sur le tri à n = 106, k = 10 : 6×, pas plus. Nommer quickselect (O(n) moyen).
  5. Clés bornées dans [0, m], m = O(n) ⇒ bucket, O(n), zéro comparaison — les fréquences le sont toujours. k ≈ n ⇒ trier.
  6. Où ça casse : un tas de taille n au lieu de k — même réponse, O(n) d'espace, et plus de flux (0,628 s contre 0,022 s en le drainant).
  7. Le silence : (−f, mot) et non (f, mot) nié après coup — nier les deux champs renverse le tri secondaire, sans erreur.
« Pour les k plus grands je garde un min-heap de taille k : son minimum est le seuil d'entrée, un élément n'entre que s'il le dépasse et prend sa place. À chaque instant le tas contient exactement les k plus grands vus, donc à la fin les k plus grands tout court, en n log k. Si les clés sont bornées, un bucket fait mieux, en linéaire. »

Chaîne verbalisée — une prise, à voix haute

5 maillons · clique pour révéler après avoir dit
  1. Pourquoi un min-heap pour les k plus grands ?
    Parce que son minimum est le plus petit des k retenus, c'est-à-dire le seuil d'entrée : tout ce qui ne le dépasse pas se jette en une comparaison, et ce qui le dépasse prend sa place en O(log k). Un max-heap donnerait accès au plus grand — dont on n'a aucun besoin.
  2. L'invariant, et le variant ?
    Après le tour i, le tas contient exactement les min(k, i+1) plus grandes valeurs de arr[0:i+1], et h[0] est la plus petite d'entre elles. Le variant est n − i, pas la taille du tas : elle monte jusqu'à k puis ne bouge plus, donc elle ne prouve rien. Le seuil, lui, est monotone croissant — c'est ce qui rend la conclusion immédiate.
  3. Complexité, et contre quoi ?
    O(n log k) en temps, O(k) en espace, et c'est le seul des trois qui tourne sur un flux. Contre O(n log n) pour un tri — à n = 10⁶ et k = 10 le gain mesuré est 6×, pas mille — et contre quickselect, O(n) en moyenne mais O(n²) au pire et il lui faut tout le tableau. En pratique la borne est lâche : 99,99 % des éléments sont rejetés par une seule comparaison.
  4. Quand le bucket bat-il le tas ?
    Quand les clés sont des entiers dans [0, m] avec m = O(n) : la clé devient un indice, on range sans comparer et on lit depuis le haut, en O(n). Le cas canonique est LC 347, parce qu'une fréquence est bornée par n. En constante c'est mince — mesuré 1,24× — et si les valeurs distinctes sont rares, allouer les seaux coûte plus cher que tout le reste.
  5. Qu'est-ce qui casse sans lever d'erreur ?
    Deux choses. Un tas de taille n au lieu de k : même réponse, mais O(n) d'espace et plus de flux — et si on le draine n − k fois, 29× plus lent. Et une clé composite dont on nie les deux champs : sur LC 692, nlargest sur (f, mot) rend pomme avant abricot alors que l'égalité de fréquence doit se trancher alphabétiquement. Il faut une égalité pour le voir, donc aucun test aléatoire ne l'attrape.