34. Heaps (Tas) : Structure Max Heap et Min Heap

Un Heap est une structure de données spécialisée basée sur un arbre qui satisfait la Propriété de Tas (Heap Property).

Crucialement, un Heap est généralement implémenté efficacement à l'aide d'un tableau.

Propriétés des Heaps

1. Complétude (Completeness) : Ce doit être un arbre binaire complet (tous les niveaux sont entièrement remplis, sauf éventuellement le dernier niveau, qui est rempli de gauche à droite).
2. Ordre du Tas (Heap Order) :
   • Max Heap : Pour chaque nœud, la valeur doit être supérieure ou égale aux valeurs de ses enfants (La racine détient l'élément maximum).
   • Min Heap : Pour chaque nœud, la valeur doit être inférieure ou égale aux valeurs de ses enfants (La racine détient l'élément minimum).

Pourquoi les Heaps sont-ils Utiles ?

Les Heaps sont essentiels pour implémenter des files de priorité et pour exécuter efficacement des algorithmes comme le Heap Sort et l'algorithme de plus court chemin de Dijkstra.

Les opérations comme l'insertion et la suppression de l'élément racine (max/min) prennent un temps O(log N).