Plan

• Files de priorité
• Représentation par tas
• Tri par tas
• Codes préfixes
• Codage de Huffman
• Codage de Huffman adaptatif

Amphi 7 1
 Files de priorité
Une file de priorité est un type abstrait de données
opérant sur un ensemble ordonné, et muni des
opérations suivantes :
• trouver le maximum,
• insérer un élément,
• retirer le maximum.

En inversant l'ordre, on obtient un type abstrait

permettant de trouver le minimum et de le retirer.

Amphi 7 2
 Files de priorité

Exemples d'utilisation :
• Ordonnancement des tâches d'un système
d'exploitation.
• Application boursière (d'après Rolf Ingold)
• Contrôle aérien
• etc.

Amphi 7 3
 Trouvé sur le Web ...
Perle donne l’avantage aux applications critiques en implantant la
gestion des niveaux de priorité sur sa gamme de routeurs.

Afin d’améliorer les performances des réseaux en fonction des applications,

Perle Systems a implanté dans ses routeurs un nouveau mode de gestion
des files d’attente. Celui-ci permet à l’administrateur réseau de définir
quatre niveaux de priorité (haute, normale, moyenne ou basse) pour une
interface ou un protocole donnés. Tous les paquets qui entrent dans le
routeur sont affectés à une file d’attente en fonction d’un degré d’urgence
défini au préalable. Les paquets affectés à la file ayant une priorité haute
sont transmis les premiers. Lorsque cette file est vide, c’est le tour des
paquets affectés à la file ayant la priorité immédiatement inférieure. Ce
système permet de ne pas retarder la transmission des données prioritaires
lorsque le réseau est encombré.

Amphi 7 4
 Trouvé aussi sur le Web: application boursière

• Une commande comprend trois champs (action, prix,

quantité), où action est un achat ou une vente, prix est le
prix proposé et quantité est le nombre d’actions.
• Une cote donne l’offre la plus haute et la demande la
plus basse.
• Lorsqu'une transaction survient, on effectue une série
de suppressions dans la liste des commandes.
• Les commandes peuvent être annulées à tout moment.

Amphi 7 5
 Structure de données pour le marché boursier

Une structure pour les offres, une pour les demandes.

Opérations supportées :

Actions Offres Demandes

Commande insere(prix, quantité) insere(prix, quantité)
Cote min() max()
Transaction retirerMin() retirerMax()
Annuler supprimer(offre) supprimer(demande)

Source: Cours du Prof. Rolf Ingold de l'université de Fribourg

Amphi 7 6
 Implantation des files de priorité

Implantation Trouver Insérer Retirer

max max
Tableau non ordonné O(n) O(1) O(n)
Liste non ordonnée O(n) O(1) O(1)*
Tableau ordonné O(1) O(n) O(1)
Liste ordonnée O(1) O(n) O(1)
Tas O(1) O(log n) O(log n)

* après avoir trouvé

Amphi 7 7
 Plan

• Files de priorité
• Représentation par tas
• Tri par tas
• Codes préfixes
• Codage de Huffman
• Codage de Huffman adaptatif

Amphi 7 8
 Arbre binaire tassé

Code : {ε, 0, 1, 00, 01,

10, 11, 000, 001, 010}
0 1
Un arbre binaire est
dit tassé si son code
0 1 0 1
est un segment initial
pour l'ordre des mots
0 1 0 croisés.

La hauteur d'un arbre tassé à n

noeuds est log2 n.
Amphi 7 9
 Structure de tas (heap en anglais)

Un tas est un arbre binaire tassé tel que le contenu de

chaque nœud soit supérieur ou égal à celui de ses fils.

23

15 7

12 5 6 1

4 8 2
Amphi 7 10
 Représentation par tableau
Numéro d'un nœud (en largeur) = indice du tableau
0
23 Racine : nœud 0
1 2 Pour un nœud i,
15 7 Parent : (i-1)/2
Fils gauche : 2i+1
3 4 5 6
12 5 6 1
Fils droit : 2i+2

7 8 9 0 1 2 3 4 5 6 7 8 9 10 11
4 8 2 23 15 7 12 5 6 1 4 8 2 11 3

Amphi 7 11
 Les tas en Java
class Tas
{
int[] a;
int nTas;
Tas(int n) {...}
int maximum() {...}
void ajouter(int v) {...}
void supprimer() {...}
}

0 1 2 3 4 5 6 7 8 9 10 11
23 15 7 12 5 6 1 4 8 2 11 3

Amphi 7 12
 Constructeur

Le constructeur crée un tableau

class Tas
{
int[] a;
int nTas;
Tas(int n)
{
nTas = 0;
a = new int[n];
}
...
}
Amphi 7 13
 Maximum

Le maximum est le contenu de la racine.

class Tas {...

int maximum()
{
return a[0];
}
}

Complexité : O(1).
0 1 2 3 4 5 6 7 8 9 10 11
23 15 7 12 5 6 1 4 8 2 11 3

Amphi 7 14
 Insertion
0
23 • Placer le nouveau
nœud dans la première
1 2 position libre (10)
15 7 • Permuter avec le
parent jusqu'à
3 4 5 6 l'obtention d'un tas
12 5 6 1

7 8 9 10 Complexité : 0(log n)
4 8 2 21
0 1 2 3 4 5 6 7 8 9 10 11
23 15 7 12 5 6 1 4 8 2 21

Amphi 7 15
 Après insertion de 21

0
23

1 2
21 7

3 4 5 6
12 15 6 1

7 8 9 10
4 8 2 5 0 1 2 3 4 5 6 7 8 9 10 11
23 21 7 12 15 6 1 4 8 2 5

Amphi 7 16
 Insertion en Java

void ajouter(int v)
{
int i = nTas;
++nTas;
while (i > 0 && a[(i-1)/2] <= v)
{
a[i] = a[(i-1)/2];
i = (i-1)/2;
}
a[i] = v;
}

Amphi 7 17
 Retirer le maximum

0 • Donner à la racine la
16 valeur du dernier nœud.
• Supprimer le dernier
1 2
nœud.
15 11
• Echanger avec le plus
3 4 5 6 grand fils jusqu'à
8 14 9 3 l'obtention d'un tas.

7 8 9 10 Complexité : O(log n)
2 4 7 10
0 1 2 3 4 5 6 7 8 9 10 11
16 15 11 8 14 9 3 2 4 7 10 3

Amphi 7 18
 Retirer le maximum

0
10

1 2
15 11

3 4 5 6
8 14 9 3

7 8 9
2 4 7

Amphi 7 19
 En Java
void supprimer() {
int v = a[0] = a[--nTas];
int i = 0;
while (2*i + 1 < nTas) {
int j = 2*i + 1;
if (j + 1 < nTas && a[j+1] > a[j])
++j;
if (v >= a[j]) break;
a[i] = a[j];
i = j;
}
a[i] = v;
}
Amphi 7 20
 Plan

• Files de priorité
• Représentation par tas
• Tri par tas
• Codes préfixes
• Codage de Huffman
• Codage de Huffman adaptatif

Amphi 7 21
 Tri par tas (heapsort)

On part d'un tableau vide a. On commence par

construire un tas en ajoutant successivement au
tas vide les éléments a[0], a[1], ...

On répète ensuite les opérations suivantes :

- prendre le maximum,
- le retirer du tas,
- le mettre à droite du tas

Complexité : O(n log n)

Amphi 7 22
 Trier (9, 2, 11, 7, 4, 14, 3, 16, 8, 10, 15)
On ajoute un à un les éléments:

9 9 11 11 11 14

2 2 9 7 9 7 9 7 11

2 2 4 2 4 9

...
Amphi 7 23
 Trier (5, 2, 11, 7, 4, 14, 3, 16, 8, 10, 15)

0 Une fois le tas obtenu...

16

1 2
15 11

3 4 5 6
8 14 9 3

7 8 9 10
2 4 7 10
0 1 2 3 4 5 6 7 8 9 10
16 15 11 8 14 9 3 2 4 7 10

Amphi 7 24
 Trier (5, 2, 11, 7, 4, 14, 3, 16, 8, 10, 15)

0 On retire les éléments un à un.

15

1 2
14 11

3 4 5 6
8 10 9 3

7 8 9
2 4 7
0 1 2 3 4 5 6 7 8 9 10
15 14 11 8 10 9 3 2 4 7 16

Amphi 7 25
 Trier (5, 2, 11, 7, 4, 14, 3, 16, 8, 10, 15)

0 On retire les éléments un à un.

14

1 2
10 11

3 4 5 6
8 7 9 3

7 8
2 4
0 1 2 3 4 5 6 7 8 9 10
14 10 11 8 7 9 3 2 4 15 16

Amphi 7 26
 Trier (5, 2, 11, 7, 4, 14, 3, 16, 8, 10, 15)

0 On retire les éléments un à un.

11

1 2
10 9

3
8
4
7
5
4
6
3
...
7
2
0 1 2 3 4 5 6 7 8 9 10
11 10 9 8 7 4 3 2 14 15 16

Amphi 7 27
 Tri par tas (heapsort) en Java
static int[] triParTas(int[] a)
{
int n = a.length;
Tas t = new Tas(n);
for (int i = 0; i < n; i++)
t.ajouter(a[i]);
for (int i = n-1; i >= 0; --i)
{
int v = t.maximum();
t.supprimer();
a[i] = v;
}
return a;
}
Amphi 7 28
 Plan

• Files de priorité
• Représentation par tas
• Tri par tas
• Codes préfixes
• Codage de Huffman
• Codage de Huffman adaptatif

Amphi 7 29
 Codes préfixes

Un ensemble P de mots non vides est un code préfixe

si aucun mot de P n'est préfixe propre d'un autre mot
de P.
Exemple : P = {0, 100, 101, 111, 1100, 1101}
Un mot admet au plus une décomposition comme
produit de mots de P. La décomposition, si elle existe,
s'obtient en lisant le mot de gauche à droite.
101010110111010110001010101001010100

Amphi 7 30
 Codes préfixes
Un ensemble fini de mots
est un code préfixe si et
seulement si c'est le code
des feuilles d'un arbre 0 1
binaire.
0 1 0 1

Code des feuilles :

0 1 0
{00, 010, 101, 110}

Amphi 7 31
 Codes préfixes

Un code préfixe P est complet si tout mot est

préfixe d'un produit de mots de P.
Le code préfixe
{0, 100, 101, 111, 1100, 1101}
est complet :
1001010101011110110011011100101110
On peut compléter ce mot par 1.

Amphi 7 32
 Codes préfixes complets
Un arbre binaire est dit
complet si ses nœuds 0 1
internes sont d'arité 2.
0 1 0 1

Un arbre binaire est

complet ssi le code de 0 1
ses feuilles est un code
préfixe complet.
Code des feuilles :
{00, 010, 011, 10, 11}
Amphi 7 33
 Codage par code préfixe

Codage :
a --> 00 d --> 10 0 1
b --> 010 r --> 11
c --> 011
0 1 0 1
Décodage : unique par a d r
lecture de gauche à 0 1
droite. b c
abracadabra <-->
0001011000110010000101100
Amphi 7 34
 Plan

• Files de priorité
• Représentation par tas
• Tri par tas
• Codes préfixes
• Codage de Huffman
• Codage de Huffman adaptatif

Amphi 7 35
 Compression de Huffman
Problème. Coder un texte à l'aide d'un code préfixe en
minimisant la taille du texte codé.
Exemples avec abracadabra
(1) a : 00, b : 010, c : 011, d : 10, r : 11.
0001011000110010000101100 --> 25
(2) a : 1, b : 000, c : 0010, d : 0011, r : 01
10000110010100111000011 --> 23
Remarque. La taille ne dépend que de la fréquence
d'apparition de chaque lettre. 5 a, 2 b, 1 c, 1 d, 2 r
Amphi 7 36
 Construction de l'arbre de Huffman (1)
Initialisation. Pour chaque lettre, un arbre réduit à sa
racine. Sa valeur est la fréquence de la lettre.

5 2 1 1 3
a b c d e

Itération. On fusionne les deux

arbres de valeur minimale. La
2
nouvelle racine a pour valeur la
somme des valeurs des racines 1 1
des deux arbres. c d
Amphi 7 37
 Construction de l'arbre de Huffman (2)

5 2 2 3 5 4 3
a b e a e
1 1 2 2
(1) c d b
1 1
12 c d
5 7 (2)
a 5 7
4 3 a Codage
(3) e 4 3 a=0
2 2 e b = 100
b 2 2
c = 1010
1 1 b d = 1011
c d 1 1
(4) c e = 11
Amphi 7
d 38
 Utilisation de l'algorithme de Huffman.

• Le codage de Huffman donne un code préfixe

optimal. (admis)
• Utilisé dans le fax et dans JPEG (compression
d'images)
• On peut coder par groupes de 2 lettres ou plus
(bitmaps).
• Il y a des techniques de compression sans perte de
données nettement plus efficaces (codage
arithmétique, Ziv-Lempel, etc.)

Amphi 7 39
 Choix de la représentation de données.

• Si la taille de l'alphabet est N, l' arbre de Huffman est

de taille 2N-1. On le représente ici par un tableau, où
(le père de la racine est 0)
j si i est fils droit de j
pere[i] =
-j si i est fils gauche de j
La création de l'arbre est contrôlée par un tas-min,
dont les clés sont les fréquences des lettres.
• Note : on pourrait aussi utiliser deux files.

Amphi 7 40
 Huffman en Java (1)
class Huffman { // Arbre à 2N - 1 nœuds
final static int N = 26, M = 2*N - 1;
static int[] pere = new int[M];
static int[] freq = new int[M];

public static void main(String[] args)

{
String s = args[0] ;
calculFrequences(s);
creerArbre();
String[] tas = faireTable();
afficherCode(s, table);
}
}
Amphi 7 41
 Calcul des fréquences
static void calculFrequences(String s)
{
for (int i = 0; i < s.length(); i++)
freq[s.charAt(i) - 'a']++;
}
static int nombreLettres()
{
int n = 0;
for (int i = 0; i < N; i++)
if (freq[i] > 0)
n++;
return n;
}
Amphi 7 42
 Un tas-min avec clés

• Un tas-min est un tas pour l'ordre > . Autrement

dit, le minimum est à la racine et le contenu de
chaque nœud est inférieur au contenu de son fils
gauche et de son fils droit.

• Un tas avec clés gère des données avec priorités :

– les données sont dans le tableau (ici tas)
– les priorités sont dans un deuxième tableau (ici
freq)

Amphi 7 43
 Un tas-min avec clés en Java
class Tas
{
int[] tas; // contient les caractères
int nTas = 0;
int[] freq; // fréquences des caractères

Tas(int taille, int[] freq)

{
this.freq = freq;
nTas = 0;
tas = new int[taille];
}
...
}
Amphi 7 44
 Ajouter à un tas-min (avec clé)
void ajouter(int v)
{
int i = nTas;
++nTas;
while (i > 0 &&
freq[tas[(i-1)/2]] >= freq[v])
{
tas[i] = tas[(i-1)/2];
i = (i-1)/2;
}
tas[i] = v;
}
Amphi 7 45
 Supprimer dans un tas-min (avec clé)
void supprimer() {
int v = tas[0] = tas[--nTas];
int i = 0;
while (2*i + 1 < nTas) {
int j = 2*i + 1;
if (j + 1 < nTas &&
freq[tas[j+1]] < freq[tas[j]])
++j;
if (freq[v] <= freq[tas[j]]) break;
tas[i] = tas[j];
i = j;
}
tas[i] = v;
} Amphi 7 46
 Minimum

int minimum()
{
return tas[0];
}

Amphi 7 47
 Création de l'arbre

static void creeArbre()

{
int n = nombreLettres();
Tas tas = new Tas(2*n - 1, freq);
for (int i = 0; i < N; ++i)
if (freq[i] > 0)
tas.ajouter(i);
int n = tas.nTas;
// A suivre ...
}

Amphi 7 48
 Création de l'arbre (2)
static void creeArbre() { // ...
for (int i = N; i < N+n-1; ++i)
{
int x = tas.minimum();
tas.supprimer();
int y = tas.minimum();
tas.supprimer();
freq[i] = freq[x] + freq[y];
pere[x] = -i;
pere[y] = i;
tas.ajouter(i);
}
}
Amphi 7 49
 Codage

static String code(int i)

{
if (pere[i] == 0)
return "";
return code(Math.abs(pere[i])) +
((pere[i] < 0) ? 0 : 1);
}

Amphi 7 50
 Transmission du code. Première solution

a : 0
b : 1010
a
c : 100
d : 1011 e
e : 11
c

b d
On code le parcours préfixe :
nœud interne 0, feuille 1
01[a]001[c]01[b]1[d]1[e]
où [x] est le code ASCII de x.
Amphi 7 51
 Transmission du code. Deuxième solution

a : 1 123 18
b : 0101 80 a 43 11 a 7
c : 011
d : 0100 e 41 39 e 6 5
e : 00 25 c 14 3 c 2

d 13 b 12 d 2 b 1

On calcule, puis on transmet des fréquences fictives

donnant le même code de Huffman ! Ici 7, 1, 2, 2, 6,
codées sur un petit nombre de bits.
Amphi 7 52
 Plan

• Files de priorité
• Représentation par tas
• Tri par tas
• Codes préfixes
• Codage de Huffman
• Codage de Huffman adaptatif

Amphi 7 53
 L'algorithme de Huffman adaptatif.

Inconvénients de l'algorithme de Huffman.

• Il faut lire le texte entièrement avant de lancer la
compression.
• Il faut transmettre le code trouvé.
La version adaptative corrige ces défauts. Principe :
• On envoie le code d'un caractère c.
• La fréquence de c est incrémentée. On met à jour
l'arbre de Huffman (voir plus loin).
• Le décodage mime le codage (même mise à jour).
Amphi 7 54
 Mise à jour de l'arbre.

On maintient une liste de parcours des nœuds

- compatible avec l'ordre des clés
- dans lequel deux frères sont toujours consécutifs.
32 11
On démontre que, dans 9 11 21 10
un arbre de Huffman, on a
peut toujours trouver un 7 10 11 8

ordre de parcours 4 5 3 5 6 6 5 5
possédant ces c e f
propriétés. 2 3 1 2
b d
Amphi 7 55
 Mise à jour après incrémentation.

Deux types d'opérations

• Partant de la feuille dont la clé est incrémentée, on
remonte vers la racine en incrémentant les clés des
nœuds rencontrés.
• Avant l'incrémentation, chaque nœud est permuté
avec le dernier nœud de même clé dans l'ordre de
parcours.

Amphi 7 56
 Mise à jour après incrémentation.

32 11 32 11

9 11 21 10 9 11 21 10
a a
7 10 11 8 7 10 11 8

3 5 4 5 6 6 5 5 3 5 4 5 6 6 6 5
c e f f c e
2 3 1 3 2 3 1 3
b d b d
Après incrément du nœud 1, Après incrément du nœud 5,
avant incrément de son père. avant incrément de son père.
Amphi 7 57
 Mise à jour après incrémentation.

33 11

12 9 21 10

6 6 6 5 7 10 8 11
e a
2 3 1 3 3 5 4 5
b d f c

Après incrément des nœuds 1, 5, 9, 11.

Le nouvel ordre de parcours vérifie bien
les deux propriétés.
Amphi 7 58
 Algorithme de Huffman. Statistiques
Contes de Grimm Données techniques
Bits 700 000 700 000
Huffman 439 613 518 361
+ Code 522 954
Total 440 135 519 315
H. Adaptatif 440 164 519 561
Codage par digrammes
Huffman 383 264 442 564
+ Code 10 880 31 488
Total 394 144 474 052
H. Adaptatif 393 969 472 534
Amphi 7 59