La collection BinaryHeap<T>

1. Présentation

Pour expliquer cette collection, il nous faut préciser ce qu’est un tas binaire. On peut voir un tas binaire comme un arbre binaire, c’est-à-dire un arbre dans lequel chaque élément a deux enfants (sauf pour les terminaisons).

Être un arbre binaire apparaît comme une condition nécessaire mais pas suffisante. L’autre condition est qu’il existe une relation d’ordre entre un nœud parent et ses deux enfants :

  • Si la relation d’ordre est « supérieur ou égal », alors le nœud parent est supérieur ou égal à ses deux enfants. On parle alors d’un tas binaire-max.

  • Si la relation d’ordre est « inférieur ou égal à », alors le nœud parent est inférieur ou égal à ses deux enfants. On parle alors d’un tas binaire-min.

C’est un type de collection particulièrement utile et performant dès lors qu’il s’agit de manipuler des files d’attente ou de priorité. En effet, il est aisé d’insérer un élément ou de rechercher le maximum ou le minimum. Nettement plus performant que si on utilisait un vecteur par exemple, ou une liste chaînée.

Voici un exemple graphique de tas binaire-max :

images/11EP3.png

Une instance de tas binaire-max

On constate qu’à chaque niveau le nœud parent est supérieur à...

Pour consulter la suite, découvrez le livre suivant :
couv_EIRUST.png
60-signet.svg
En version papier
20-ecran_lettre.svg
En version numérique
41-logo_abonnement.svg
En illimité avec l'abonnement ENI
130-boutique.svg
Sur la boutique officielle ENI
Précédent
La collection LinkedList<T>
Suivant
Table de hachage HashMap<Key, Value>