3.3 Tri d’un ensemble de clés
91
un arbre binaire de recherche : le nombre d’appels récursifs pour trouver une clé
est égal à la profondeur du nœud où la recherche s’arrête, dans l’arbre binaire
de recherche correspondant (voir par exemple l’article de Martinez, Panholzer et
Prodinger [181]).
Si nous nous intéressons au nombre moyen de comparaisons pour trouver une clé
de rang p dans un tableau de taille n, lorsque toutes les valeurs de p sont supposées
équiprobables, nous pouvons montrer que ce nombre moyen est inférieur ou égal
à 4n (cf. Knuth [156, p. 136]).
Il existe, là aussi, des variantes quant au choix du pivot, qui peut être choisi
comme médiane de éléments ; la plus simple est de prendre la médiane de trois
clés, mais certaines stratégies sont plus élaborées et tiennent compte du rapport
p
n
pour choisir le pivot (cf. Martinez, Panario et Viola [182]).
3.3.3 Tas, files de priorité, et tri par tas
Rappelons (cf. section 1.2.4) qu’un tas est un arbre binaire parfait croissant ; nous
en donnons un exemple en figure 3.21. Nous supposons dans cette section que
les clés sont organisées suivant une structure de tas, qui est lui-même représenté
en mémoire par un tableau. Les opérations que cette structure permet d’effectuer
aisément sont l’insertion d’une clé, l’obtention du minimum, et sa suppression suivie
de la reconstruction de la structure de tas. Les détails de l’implémentation d’un tas
dans un tableau ainsi que les algorithmes de mise à jour du tas sont donnés dans la
section A.6.3.
Les tas permettent par exemple d’implémenter une file de priorité, i.e., une
structure de données où la clé correspond à une notion de priorité, tout comme une
file d’attente avec certains clients prioritaires qui passent en premier, et d’autres
clients qui attendent sagement leur tour. Les opérations permises sont l’arrivée
d’un client et son insertion dans la file suivant sa priorité, le choix du client le
plus prioritaire, et son départ une fois qu’il a été servi. Les tas servent aussi pour
une méthode de tri par comparaison d’un ensemble de clés : c’est le tri par tas,
qui construit d’abord un tas contenant toutes les clés, puis supprime les minima
successifs, et fournit donc les clés triées en ordre croissant. Nous renvoyons là
encore à la section A.6.3 pour l’algorithme adéquat.
Fig. 3.21 Un tas de taille 9
sur les données {1, . . . , 9}
91
un arbre binaire de recherche : le nombre d’appels récursifs pour trouver une clé
est égal à la profondeur du nœud où la recherche s’arrête, dans l’arbre binaire
de recherche correspondant (voir par exemple l’article de Martinez, Panholzer et
Prodinger [181]).
Si nous nous intéressons au nombre moyen de comparaisons pour trouver une clé
de rang p dans un tableau de taille n, lorsque toutes les valeurs de p sont supposées
équiprobables, nous pouvons montrer que ce nombre moyen est inférieur ou égal
à 4n (cf. Knuth [156, p. 136]).
Il existe, là aussi, des variantes quant au choix du pivot, qui peut être choisi
comme médiane de éléments ; la plus simple est de prendre la médiane de trois
clés, mais certaines stratégies sont plus élaborées et tiennent compte du rapport
p
n
pour choisir le pivot (cf. Martinez, Panario et Viola [182]).
3.3.3 Tas, files de priorité, et tri par tas
Rappelons (cf. section 1.2.4) qu’un tas est un arbre binaire parfait croissant ; nous
en donnons un exemple en figure 3.21. Nous supposons dans cette section que
les clés sont organisées suivant une structure de tas, qui est lui-même représenté
en mémoire par un tableau. Les opérations que cette structure permet d’effectuer
aisément sont l’insertion d’une clé, l’obtention du minimum, et sa suppression suivie
de la reconstruction de la structure de tas. Les détails de l’implémentation d’un tas
dans un tableau ainsi que les algorithmes de mise à jour du tas sont donnés dans la
section A.6.3.
Les tas permettent par exemple d’implémenter une file de priorité, i.e., une
structure de données où la clé correspond à une notion de priorité, tout comme une
file d’attente avec certains clients prioritaires qui passent en premier, et d’autres
clients qui attendent sagement leur tour. Les opérations permises sont l’arrivée
d’un client et son insertion dans la file suivant sa priorité, le choix du client le
plus prioritaire, et son départ une fois qu’il a été servi. Les tas servent aussi pour
une méthode de tri par comparaison d’un ensemble de clés : c’est le tri par tas,
qui construit d’abord un tas contenant toutes les clés, puis supprime les minima
successifs, et fournit donc les clés triées en ordre croissant. Nous renvoyons là
encore à la section A.6.3 pour l’algorithme adéquat.
Fig. 3.21 Un tas de taille 9
sur les données {1, . . . , 9}