Heap : accéder au min/max en O(1)

Un tas (heap) est un arbre binaire presque complet qui respecte une propriété d'ordre : dans un min-heap, chaque parent est plus petit que ses enfants (le minimum est donc toujours à la racine) ; dans un max-heap, chaque parent est plus grand (le maximum à la racine).

Contrairement à un BST, un heap n'est pas trié en profondeur — aucune garantie entre nœuds frères. En contrepartie, il s'implémente en général sur un simple tableau (pas de pointeurs) : les enfants du nœud à l'index i se trouvent en 2i+1 et 2i+2.

Complexités clés : accéder au min/max coûte O(1) (c'est la racine) ; insérer ou retirer le min/max coûte O(log n) (il faut « remonter » ou « redescendre » l'élément pour rétablir la propriété de tas) ; construire un heap à partir d'un tableau coûte O(n) — pas O(n log n), grâce à un algorithme de construction du bas vers le haut.

Cas d'usage typiques : trouver les k plus grands ou plus petits éléments (en gardant un heap de taille k), une file de priorité (traiter les tâches par priorité plutôt que par ordre d'arrivée), fusionner k listes triées, ou le plus court chemin (Dijkstra, vu en Phase 3).

Dans la plupart des langages, une implémentation existe déjà : `heapq` en Python (min-heap par défaut), `PriorityQueue` en Java. En JavaScript, il n'y a pas de heap natif — il faut soit l'implémenter, soit passer par une librairie.

Vidéo

Quiz