Partie 4

Structures de données élémentaires

Structures de données élémentaires 163

Plan

1. Introduction

2. Pile

3. Files simple et double

4. Liste

5. Vecteur

6. File à priorité

Structures de données élémentaires 164

Concept

Une structure de données est une manière d’organiser et de stocker

l’information
I Pour en faciliter l’accès ou dans d’autres buts
Une structure de données a une interface qui consiste en un
ensemble de procédures pour ajouter, e↵acer, accéder, réorganiser,
etc. les données.
Une structure de données conserve des données et éventuellement
des méta-données
I Par exemple : un tas utilise un tableau pour stocker les clés et une
variable A.heap-size pour retenir le nombre d’éléments qui sont dans
le tas.
Un type de données abstrait (TDA) = définition des propriétés de la
structure et de son interface (“cahier des charges”)

Structures de données élémentaires 165

Structures de données

Dans ce cours :
Principalement des ensembles dynamiques (dynamic sets), amenés à
croı̂tre, se rétrécir et à changer au cours du temps.
Les objets de ces ensembles comportent des attributs.
Un de ces attributs est une clé qui permet d’identifier l’objet, les
autres attributs sont la plupart du temps non pertinents pour
l’implémentation de la structure.
Certains ensembles supposent qu’il existe un ordre total entre les
clés.

Structures de données élémentaires 166

Opérations standards sur les structures

Deux types : opérations de recherche/accès aux données et

opérations de modifications
Recherche : exemples :
I Search(S, k) : retourne un pointeur x vers un élément dans S tel
que x.key = k, ou NIL si un tel élément n’appartient pas à S.
I Minimum(S), Maximum(S) : retourne un pointeur vers l’élément
avec la plus petite (resp. grande) clé.
I Successor(S, x),Predecessor(S, x) retourne un pointeur vers
l’élément tout juste plus grand (resp. petit) que x dans S, NIL si x
est le maximum (resp. minimum).
Modification : exemples :
I Insert(S, x) : insère l’élément x dans S.
I Delete(S, x) : retire l’élément x de S.

Structures de données élémentaires 167

Implémentation d’une structure de données

Etant donné un TDA (interface), plusieurs implémentations sont

généralement possibles
La complexité des opérations dépend de l’implémentation, pas du
TDA.

Les briques de base pour implémenter une structure de données

dépendent du langage d’implémentation
I Dans ce cours, les principaux outils du C : tableaux, structures à la C
(objets avec attributs), liste liées (simples, doubles, circulaires), etc.
Une structure de données peut être implémentée à l’aide d’une autre
structure de données (de base ou non)

Structures de données élémentaires 168

Quelques structures de données standards

Pile : collection d’objets accessible selon une politique LIFO

File : collection d’objets accessible selon une politique FIFO
File double : combine accès LIFO et FIFO
Liste : collection d’objets ordonnés accessible à partir de leur position
Vecteur : collection d’objets ordonnés accessible à partir de leur rang
File à priorité : accès uniquement à l’élément de clé (priorité)
maximale

Dictionnaire : structure qui implémente les 3 opérations recherche,

insertion, suppression (cf. partie 5)

Structures de données élémentaires 169

Pile

Ensemble dynamique d’objets accessibles selon une discipline LIFO

(“Last-in first-out”).
Interface
I Stack-Empty(S) renvoie vrai si et seulement si la pile est vide
I Push(S, x) pousse la valeur x sur la pile S
I Pop(S) extrait et renvoie la valeur sur le sommet de la pile S
Applications :
I Option ’undo’ dans un traitement de texte
I Langage postscript
I Appel de fonctions dans un compilateur
I ...
Implémentations :
I avec un tableau (taille fixée a priori)
I au moyen d’une liste liée (allouée de manière dynamique)
I ...

Structures de données élémentaires 170

Implémentation par un tableau

S est un tableau qui contient les éléments de la pile

S.top est la position courante de l’élément au sommet de S
Implémentation par un tableau
4 9 5
S est un tableau qui contientStack-Empty(S)
les éléments de la pile
S.top est la position courante return
1 de S.top ==
l’élément au 0sommet de

Pop(S)
Stack-Empty(S)
Push(S, x)
11 ifif S.top
Stack-Empty(S)
== 0
1 if S.top == S.length 2 error “underflow”
2 error “overflow” 2 return true
else return
33 else S.top = S.top 1
false
3 S.top = S.top + 1 4 return S[top(S) + 1]
4 S[S.top] = x
ComplexitéPush(S,
en temps x) et en espace : O(1) Pop(S)
(Inconvénient : L’espace occupé
1 S.top = S.top + 1 ne dépend pas du nombre d’objets)
1 if Stack-Emp
2 S[S.top] = x 2 error “und
3 else S.top = S
Structures de données élémentaires 171
 10.2 Linked lists 237
Rappel : liste simplement et doublement liée
prev key next

(a) L:head 9 16 4 1

(b) L:head 25 9 16 4 1
Structure de données composée d’une séquence d’éléments de liste.
(c)
Chaque élément x de25 la liste est9 composé16:
L:head 1

I d’un contenu utile x.data de type arbitraire (par exemple une clé),
I Figure 10.3 x.next
d’un pointeur (a) A doubly linked
vers list L representing
l’élément the dynamic
suivant dansset la 9; 16g. Each element in
séquence
f1; 4;
I the list is an object with attributes for the key and pointers (shown by arrows) to the next and previous
Doublement liée : d’une pointeur x.prev vers l’élément précédent
objects. The next attribute of the tail and the pre! attribute of the head are NIL , indicated by a diagonal
dans laslash. The attribute L: head points to the head. (b) Following the execution of L IST-I NSERT.L; x/,
séquence
where x: key D 25, the linked list has a new object with key 25 as the new head. This new object
Soit L unepoints
listeto the
liée
old head with key 9. (c) The result of the subsequent call L IST-D ELETE.L; x/, where x
points to the object with key 4.
I L.head pointe vers le premier élément de la liste
I Doublement
elements.liée : L.tail
In the pointe
remainder of this vers le we
section, dernier
assumeélément dewith
that the lists la which
liste we
Le dernier are working are
élément unsorted un
possède and doubly linked.x.next vide (noté NIL)
pointeur
Searching
Doublement liée : aLe
linked list
premier élément possède un pointeur x.prev
vide The procedure L IST-S EARCH .L; k/ finds the first element with key k in list L
by a simple linear search, returning a pointer to this element. If no object with
key k appears in the list, then the procedure returns NIL. For the linked list in
Figure 10.3(a), the call L IST-S EARCH .L; 4/ returns a pointer to the third element,
Structures de données élémentaires 172
 ecution of L IST-I NSERT.L; x/,
heImplémentation
new head. This newd’uneobject pile à l’aide d’une liste liée
L IST-D ELETE.L; x/, where x
S est une liste simplement liée (S.head pointe vers le premier
à l’aide d’une liste liée
élément de la liste)
ément dewith
at the lists la which
liste we Stack-Empty(S)
liée (S.head pointe
9 vers le14premier 1 if S. head = = NIL
de (noté NIL) 2 return true
3 else return false
pointeur x.prev
ack-Empty(S)
4
Pop(S)
ment with key
if S.head k in list L
== NIL 1 if Stack-Empty(S)
ement. If no object with
Push(S,
return x)
true 2 error “underflow”

. For the false

linked list in
1 x.next = S.head 3 else x = S.head
IL
else return 4 S. head = S. head.next
2 S.head = x
inter to the third element, 65 5 return x

Complexité en temps O(1), complexité en espace O(n) pour n

Pop(S)
opérations
1 if Stack-Empty(S)
2
Structures de données élémentaires
error “underflow” 173
Application
Vérifier l’appariement de parenthèses ([],() ou {}) dans une chaı̂ne
de caractères
I Exemples : ((x) + (y )]/2 ! non, [ (b) + sqrt(4 ⇤ (a) ⇤ c)]/(2 ⇤ a) !
oui
Solution basée sur une pile :
ParenthesesMatch(A)
1 S = pile vide
2 for i = 1 to A.length
3 if A[i] est une parenthèse gauche
4 Push(S, A[i])
5 elseif A[i] est une parenthèse droite
6 if Stack-Empty(S)
7 return False
8 elseif Pop(S) n’est pas du même type que A[i]
9 return False
10 return Stack-Empty(S)

Structures de données élémentaires 174

File

Ensemble dynamique d’objets accessibles selon une discipline FIFO

(“First-in first-out”).
Interface
I Enqueue(Q, s) ajoute l’élément x à la fin de la file Q
I Dequeue(Q) retire l’élément à la tête de la file Q

Implémentation à l’aide d’un tableau circulaire

I Q est un tableau de taille fixe Q.length
I Mettre plus de Q. length éléments dans la file provoque une erreur de
dépassement
I Q.head est la position à la tête de la file
I Q.tail est la première position vide à la fin de la file
I Initialement : Q.head = Q.tail = 1

Structures de données élémentaires 175

 234
Enqueue Chapter
etChapter 10 Elementary Data Structures
Dequeue
234 10 Elementary Data Structures
234
Etat initial : Chapter 10 Elementary Data Structures
1 2 3 4 5 6 7 8 9 10 11 12
(a) Q 1 2 3 4 5 6 157 6 8 9 9 8 104 11 12
(a) Q 1 2 3 4 5 6 7 8 9 10 11 12
15 6 9 8 4
(a) Q Q:head D 7
15 6 9 8 4
Q:tail D 12
Q:head D 7 Q:tail D 12
1 2 3 4 5 6 7 8 9 10 11 12
Enqueue(Q, 17), Enqueue(Q, 3), Enqueue(Q,
Q:head D 7 5)Q:tail D 12
(b) Q 31 52 3 4 5 6
157 6 8 9 9 8 104 11
17 12

(b) Q 13 25 3 4 5 6 15 7 68 99 8
10 4
11 17
12
(b) Q 3 Q:tail
5 D 3 Q:head15D 76 9 8 4 17

1
2 3 D
Q:tail 4 3 5 Q:head
6 7 8 D 97 10 11 12
(c) Q 3 Q:tail
5 D3 15 6 D97 8 4 17
Q:head
1 2 3 4 5 6 7 8 9 10 11 12
Dequeue(Q) ! 15
(c) Q 13 25 3 4 5 6 15
7 68 99 810 411 17
12
Q:tail D 3 Q:head D 8
(c) Q 3 5 15 6 9 8 4 17
Q:tail D 3 Q:head D 8
Figure 10.2 A queue implemented using an array QŒ1 : : 12!. Queue elements appear o
lightly shaded D 3 (a) TheQ:head
positions.
Q:tail queue hasD5 8elements, in locations QŒ7 : : 11!. (b) The con
of the queue after the calls E NQUEUE.Q; 17/, E NQUEUE.Q; 3/, and E NQUEUE.Q; 5/
Figure 10.2 ofA the
configuration queue implemented
queue using
after the call an array
D EQUEUE .Q/QŒ1returns theQueue
: : 12!. elements
key value ap
15 forme
lightly shaded
Structures de données élémentaires positions. (a) The queue has 5 elements, in locations QŒ7 : : 11!. (b)
176 T
Enqueue et Dequeue

Enqueue(Q,x) Dequeue(Q)
1 Q[Q.tail] = x 1 x = Q[Q.head]
2 if Q.tail == Q.length 2 if Q.head == Q.length
3 Q.tail = 1 3 Q.head = 1
4 else Q.tail = Q.tail + 1 4 else Q.head = Q.head + 1
5 return x

Complexité en temps O(1), complexité en espace O(1).

Exercice : ajouter la gestion d’erreur

Structures de données élémentaires 177

 Soit la file double Q :
Implémentation à l’aide d’une liste liée
I Q.head pointe vers un
I Q.tail pointe vers un
Soit la file double Q :
I
Q.head pointe
9 vers un14 4
I
Q.tail pointe vers un
Q est une liste simplement liée
Q.head (resp. Q.tail) pointe vers la tête (resp. la queue) de la liste
Enqueue(Q,x) Dequeue(Q)
1 x.next = NIL 1 if Q.head == NIL
2 if Q.head == NIL 2 error “underflow”
3 Q.head = x 3 x = Q.head
4 else Q.tail.next = x 4 Q.head = Q.head.next
5 Q.tail = x 5 if Q.head == NIL
6 de données
Structures Q.tail = NIL
élémentaires
7 return x
Structures de données élémentaires
Complexité en temps O(1), complexité en espace O(n) pour n
opérations

Structures de données élémentaires 178

File double

Double ended-queue (deque)

Généralisation de la pile et de la file

Collection ordonnée d’objets o↵rant la possibilité
I d’insérer un nouvel objet avant le premier ou après le dernier
I d’extraire le premier ou le dernier objet
Interface :
I insert-first(Q, x) : ajoute x au début de la file double
I insert-last(Q, x) : ajoute x à la fin de la file double
I remove-first(Q) : extrait l’objet situé en première position
I remove-last(Q) : extrait l’objet situé en dernière position
I ...
Application : équilibrage de la charge d’un serveur

Structures de données élémentaires 179

 Implémentation par u
Implémentation à l’aide d’une liste doublement liée
mplémentation par une liste doublement liée
A l’aide d’une liste double liée
Soit la file double Q :
I Q.head pointe vers un élément sentinelle en début de liste
I Q.tail pointe vers un élément sentinelle en fin de Soit
liste la file double Q
I Q.size est la taille courante de la liste I Q.head pointe ver
I Q.tail pointe vers
Soit la file double Q :
I Q.head pointe vers un 9 14 4
I Q.tail pointe vers un
Les sentinelles ne contiennent pas de données. Elles permettent de
simplifier le code (pour un coût en espace constant).

Exercice : implémentation de la file double sans sentinelles,

implémentation de la file simple avec sentinelle

Structures de données élémentaires Structures de données élémentaires 180

Implémentation à l’aide d’une liste doublement liée
insert-first(Q, x) insert-last(Q, x)
1 x.prev = Q.head 1 x.prev = Q.tail.prev
2 x.next = Q.head.next 2 x.next = Q.tail
3 Q.head.next.prev = x 3 Q.tail.prev .next = x
4 Q.head.next = x 4 Q.head.prev = x
5 Q.size = Q.size + 1 5 Q.size = Q.size + 1

remove-first(Q) remove-last(Q)
1 if (Q.size == 0) 1 if (Q.size == 0)
2 error 2 error
3 x = Q.head.next 3 x = Q.tail.prev
4 Q.head.next = Q.head.next.next 4 Q.tail.prev = Q.tail.prev .prev
5 Q.head.next.prev = Q.head 5 Q.tail.prev .next = Q.head
6 Q.size = Q.size 1 6 Q.size = Q.size 1
7 return x 7 return x

Complexité O(1) en temps et O(n) en espace pour n opérations.

Structures de données élémentaires 181
Liste
Ensemble dynamique d’objets ordonnés accessibles relativement les
uns aux autres, sur base de leur position
Généralise toutes les structures vues précédemment
Interface :
I Les fonctions d’une liste double (insertion et retrait en début et fin de
liste)
I Insert-Before(L, p, x) : insére x avant p dans la liste
I Insert-After(L, p, x) : insère x après p dans la liste
I Remove(L, p) : retire l’élement à la position p
I replace(L, p, x) : remplace par l’objet x l’objet situé à la position p
I first(L), last(L) : renvoie la première, resp. dernière position dans
la liste
I prev(L, p), next(L, p) : renvoie la position précédant (resp. suivant)
p dans la liste

Implémentation similaire à la file double, à l’aide d’une liste

doublement liée (avec sentinelles)
Structures de données élémentaires 182
 Implémentation à l’aide d’une liste doublement liée
mplémentation à l’aide d’une liste doublement liée
p.prev p.next p x 6 remove(L, p)
1 p.prev .next = p.next
Implémentation
Implémentation ààl’aide
p, x) d’une
l’aide
Implémentation d’une liste
liste2doublement
à l’aide doublement
d’une liste liée
p, x)doublement
insert-before(L,
9 14 4
insert-after(L,
p.next.prev = p.prev liée
1 x.prev = p.prev 1 x.prev = p = L.size 1
3 L.size
p.prev
p.prev2p.next
x.nextp p=
p.next xp.prev
xp p.next p x 2 x.next = p.next
4 return p
3 p.prev .next = x 3 p.next.prev = x
4 insert-before(L,
insert-before(L,
p.prev =x insert-before(L,
p,p,x)x) p, x) = x
insert-after(L,
insert-after(L,
4 p.next insert-after(L,
p, x) p, x)
5 1L.size = L.size + 1
1 x. prev = p. prev 1 x. prev = p
x.x.
prev ==p.p.
1 insert-before(L,
prev prev
prev p, x) 5 L.size 11 x. x.=prev
L.size
prev
insert-after(L, =+
= pp 1 p, x)
2 x. next = p 2 x. next = p. next
2 2 x. next
x. next = =p p
1 x.prev = p.prev 22 x.
x. next
next =
= p.
p.next
3 p. prev .next = 1 x x.prev = p 3 p. next.prev = x
3 3 p.
2 p. prev
prev ==p=4xx p. prev
.next
.next
x.next 33 p. p.next.prev
next.prev = x
remove(L, p) = x 4 p. next = x
4 4 p.
3 p.
prev
p.prev x x 5 = L.x size = L. size24+
prev==.next 4 1x.next
p.next
p. next == xxp.next
= 5 L. size = L. size + 1
5 5 L. 1L.size
p.prev
++1.next = p.next355 p.next.prev =+ x1
4 L. size==L.
size
p.prev = size
x 1
2 p.next.prev = p.prev
L.size
L. size =
= L.L.size
5 L.size 3= L.size 4 p.next = x
L.size + = 1L.size 1
remove(L, p)
remove(L,
5 L.size = L.size + 1
p) 1 p. prev .next = p. next
4 return p
remove(L, p)
Complexité O(1) en temps et O(n)
11 p.p.prev
prev.nexten=
.next espace
2= nextpour n= opérations.
p.next
p. next.prev p. prev
Complexité O(1) en temps et O(n) en espace pour n opérations.1
2 2 p.
p. next.prev
next.prev 3
== L.
p.
p. size
prev
prev = L. size
33 L.L.size 4 return
size ==L.L.size
size 11 p
Structures de données élémentaires 183
Vecteur

Ensemble dynamique d’objets occupant des rangs entiers successifs,

permettant la consultation, le remplacement, l’insertion et la
suppression d’éléments à des rangs arbitraires
Interface
I Elem-At-Rank(V , r ) retourne l’élément au rang r dans V .
I Replace-At-Rank(V , r , x) remplace l’élément situé au rang r par
x et retourne cet objet.
I Insert-At-Rank(V , r , x) insère l’élément x au rang r , en
augmentant le rang des objets suivants.
I Remove-At-Rank(V , r ) extrait l’élément situé au rang r et le
retire de r , en diminuant le rang des objets suivants.
I Vector-Size(V ) renvoie la taille du vecteur.
Applications : tableau dynamique, gestion des éléments d’un
menu,. . .
Implémentation : liste liée, tableau extensible. . .

Structures de données élémentaires 184

Implémentation par un tableau extensible
Les éléments sont stockés dans un tableau extensible V .A de taille
initiale V .c.
En cas de dépassement, la capacité du tableau est doublée.
V .n retient le nombre de composantes.
Insertion et suppression :
Insert-At-Rank(V , r , x) Remove-At-Rank(V , r )
1 if V . n = = V . c 1 tmp = V . A[r ]
2 V .c = 2 · V .c 2 for i = r to V . n 1
3 W = “Tableau de taille V . c” 3 V . A[i] = V . A[i + 1]
4 for i = 1 to n 4 V .n = V .n 1
5 W [i] = V .A[i] 5 return tmp
6 V .A = W
7 for i = V . n downto r
8 V . A[i + 1] = V . A[i]
9 V . A[r ] = x
10 V . n = V . n + 1

Structures de données élémentaires 185

Complexité en temps
Insert-At-Rank :
I O(n) pour une opération individuelle, où n est le nombre de
composantes du vecteur
I O(n2 ) pour n opérations d’insertion en début de vecteur
I O(n) pour n opérations d’insertion en fin de vecteur
Justification :
I Si la capacité du tableau passe de c0 à 2k c0 au cours des n
opérations, alors le coût des transferts entre tableaux s’élève à

c0 + 2c0 + . . . + 2k 1
c0 = (2k 1)c0 .

Puisque 2k 1 c0 < n  2k c0 , ce coût est O(n).

I On dit que le coût amorti par opération est O(1)
I Si on avait élargi le tableau avec un incrément constant m, le coût
aurait été
k(k 1)
c0 + (c0 + m) + (c0 + 2m) + . . . + (c0 + (k 1)m) = kc0 + m.
2
Puisque c0 + (k 1)m < n  c0 + km, ce coût aurait donc été O(n2 ).
Structures de données élémentaires 186
Complexité en temps

Remove-At-Rank :
I O(n) pour une opération individuelle, où n est le nombre de
composantes du vecteur
I O(n2 ) pour n opérations de retrait en début de vecteur
I O(n) pour n opérations de retrait en fin de vecteur
Remarque : Un tableau circulaire permettrait d’améliorer l’efficacité
des opérations d’ajout et de retrait en début de vecteur.

Structures de données élémentaires 187

File à priorité

Ensemble dynamique d’objets classés par ordre de priorité

I Permet d’extraire un objet possédant la plus grande priorité
I En pratique, on représente les priorités par les clés
I Suppose un ordre total défini sur les clés
Interface :
I Insert(S, x) : insère l’élément x dans S.
I Maximum(S) : renvoie l’élément de S avec la plus grande clé.
I Extract-Max(S) : supprime et renvoie l’élément de S avec la plus
grande clé.
Remarques :
I Extraire l’élément de clé maximale ou minimale sont des problèmes
équivalents
I La file FIFO est une file à priorité où la clé correspond à l’ordre
d’arrivée des élements.
Application : gestion des jobs sur un ordinateur partagé

Structures de données élémentaires 188

Implémentations
Implémentation à l’aide d’un tableau statique
I Q est un tableau statique de taille fixée Q.length.
I Les éléments de Q sont triés par ordre croissant de clés. Q.top pointe
vers le dernier élément.
I Complexité en temps : extraction en O(1) et insertion en O(n) où n
est la taille de la file
I Complexité en espace : O(1)
Implémentation à l’aide d’une liste liée
I Q est une liste liée où les éléments sont triés par ordre décroissant de
clés
I Complexité en temps : extraction en O(1) et insertion en O(n) où n
est la taille de la file
I Complexité en espace : O(n)
Peut-on faire mieux ?
Exercice : comment obtenir O(1) pour l’insertion et O(n) pour
l’extraction ?
Structures de données élémentaires 189
Implémentation à l’aide d’un tas

La file est implémentée à l’aide d’un tas(-max) (voir slide 143)

Accès et extraction du maximum :

Heap-Maximum(A) Heap-Extract-Max(A)
1 return A[1] 1 if A.heap-size < 1
2 error “heap underflow”
3 max = A[1]
4 A[1] = A[A.heap-size]
5 A.heap-size = A.heap-size 1
6 Max-heapify(A, 1) // reconstruit le tas
7 return max

Complexité : O(1) et O(log n) respectivement (voir chapitre 3)

Structures de données élémentaires 190

 Of a max-heap. [Arcs above and below the array
Implémentation à l’aide d’un tas
and children. There is no significance to whether
the array.]
1
16
2 3
14 10
4 5 6 7 1 2

8 7 9 3 16 14
8 9 10
2 4 1

Heap property
Structures de données élémentaires 191
Implémentation à l’aide d’un tas : insertion

Increase-Key(S, x, k) augmente la valeur de la clé de x à k (on

suppose que k à la valeur courante de la clé de x).

Heap-Increase-Key(A, i, key )
1 if key < A[i]
2 error “new key is smaller than current key”
3 A[i] = key
4 while i > 1 and A[Parent(i)] < A[i]
5 swap(A[i], A[Parent(i)])
6 i = Parent(i)

Complexité : O(log n) (la longueur de la branche de la racine à i

étant O(log n) pour un tas de taille n).

Structures de données élémentaires 192

Implémentation à l’aide d’un tas : insertion

Pour insérer un élément avec une clé key :

I l’insérer à la dernière position sur le tas avec une clé 1,
I augmenter sa clé de 1 à key en utilisant la procédure précédente

Heap-Insert(A, key )
1 A.heap-size = A.heap-size + 1
2 A[A.heap-size] = 1
3 Heap-Increase-Key(A, A.heap-size, key )

Complexité : O(log n).

) Implémentation d’une file à priorité par un tas : O(log n) pour

l’extraction et l’insertion.

Structures de données élémentaires 193

Ce qu’on a vu

Quelques structures de données classiques et di↵érentes

implémentations pour chacune d’elles
I Pile
I Liste
I Files simples, doubles et à priorité
I Vecteurs
Structures de type liste liée

Structures de données élémentaires 194

Ce qu’on n’a pas vu

Structure de type séquence : hybride entre le vecteur et la liste

Notion d’itérateur
Tas binomial : alternative au tas binaire qui permet la fusion rapide
de deux tas
Evolution dynamique de la taille d’un tas (analyse amortie)
...

Structures de données élémentaires 195