Heaps (tas binaires)

Un heap donne accès au plus petit élément (min-heap) ou au plus grand (max-heap) en O(1), et permet de l'extraire ou d'insérer un nouvel élément en O(log n). C'est la structure derrière les files de priorité, le tri par heap et l'algorithme de Dijkstra.

Deux règles

1. Forme : l'arbre est presque complet. Tous les niveaux sont pleins, sauf peut-être le dernier, qui se remplit de gauche à droite.
2. Ordre : la clé d'un noeud est toujours meilleure que celles de ses enfants (plus petite dans un min-heap, plus grande dans un max-heap).

Contrairement à un ABR, il n'y a aucun ordre entre frères : un heap n'est pas trié, il garantit seulement que la racine est le minimum (ou le maximum).

Stockage dans un tableau

Comme l'arbre est presque complet, on le range niveau par niveau dans un tableau, sans pointeurs. Pour l'élément à l'indice i (en commençant à 0) :

• parent : ⌊(i − 1) / 2⌋
• enfant gauche : 2i + 1
• enfant droit : 2i + 2

Le min-heap [3, 8, 5, 12, 10, 7] correspond à cet arbre :

          3
        /   \
       8     5
      / \   /
    12  10 7

Insérer : placer puis remonter

1. On place le nouvel élément à la prochaine case libre (la fin du tableau), pour garder la forme.
2. Tant qu'il est meilleur que son parent, on les échange (percolate up).

Exemple : insérer 4 dans [3, 8, 5, 12, 10, 7]. 4 va à l'indice 6, dont le parent est l'indice 2 (5). 4 < 5 : on échange. Le nouveau parent est 3, et 4 ≥ 3 : on s'arrête. Résultat : [3, 8, 4, 12, 10, 7, 5].

EffacerMin : remplacer puis descendre

1. On retire la racine et on la remplace par le dernier élément du tableau. Retirer directement la racine laisserait un trou.
2. Tant qu'un enfant est meilleur que lui, on l'échange avec le meilleur des deux enfants (percolate down).

Exemple : EffacerMin sur [3, 8, 5, 12, 10, 7]. On retire 3 et on met 7 à la racine : [7, 8, 5, 12, 10]. Les enfants de 7 sont 8 et 5 ; le plus petit est 5, et 5 < 7 : on échange. 7 n'a plus d'enfant. Résultat : [5, 8, 7, 12, 10].

Construire un heap en O(n)

À partir d'un tableau quelconque, on pourrait insérer les éléments un par un, ce qui coûte O(n log n). Il existe mieux : on fait descendre chaque noeud interne, du dernier parent (indice ⌊n/2⌋ − 1) jusqu'à la racine.

Exemple : [9, 4, 7, 1, 8, 2], n = 6, on commence à l'indice 2.

1. Indice 2 (7) : son enfant 2 est plus petit → échange. [9, 4, 2, 1, 8, 7]
2. Indice 1 (4) : ses enfants sont 1 et 8 ; 1 < 4 → échange. [9, 1, 2, 4, 8, 7]
3. Indice 0 (9) : ses enfants sont 1 et 2 ; 1 < 9 → échange. Puis 9 a pour enfants 4 et 8 ; 4 < 9 → échange. [1, 4, 2, 9, 8, 7]

Pourquoi O(n) ? La moitié des noeuds sont des feuilles et ne bougent pas. Un quart peut descendre d'au plus 1 niveau, un huitième d'au plus 2, et ainsi de suite. La somme n/4 · 1 + n/8 · 2 + n/16 · 3 + … est bornée par n.

Complexité

Le tri par heap utilise un max-heap : on construit le heap en O(n), puis on extrait le maximum n fois, pour un total de O(n log n) sans mémoire supplémentaire.