ALGO1 – File de priorité et tas binaire

211903

ALGO1 { File de priorite et tas binaire

Francois Schwarzentruber

February 18, 2021TableauTableau trieTas binaire

enfilerO(1)O(n)O(logn) defilerO(n)O(1)O(logn)

Avantage des tas :

source d'inspiration pour de bonnes implem (comme tas de Fibonacci) d'une le de priorite tri par tas qui est en place et optimal structure en place, contrairement aux ABR qui implementent le de priorite avec la m^eme complexite

1 Arbre binaire presque complet

Denition 1 (arbre binaire presque complet)Un arbre binaire est ditpresque completsi

tous les niveaux sont complets sauf eventuellement le dernier.Exemple 2Voici un arbre binaire presque complet avec 6 nuds.7

12 25149
41
Proposition 3Un arbre binaire presque complet annuds est de hauteur6log2(n). D emonstration.SoitHla hauteur de l'arbre. Il y a 1 noeuds au niveau 0 (la racine). Il y a 2 noeuds au niveau 1 (les ls de la racine). Il y a au plus 2 `noeuds au niveau`.= 1 = 2 = 2 H111 On a 1+2+:::2H1sur les niveaux 0 aH1 et au moins un noeud sur le niveauH. Donc : 1+2+:::2H1+1n.

Autrement dit, 2

H1 + 1 = 2Hn. En passant au log, on obtient le resultat de la proposition.

2 Implementation d'un arbre binaire presque complet avec un tableau

Le tableau contient les elements d'indice croissant dans l'ordre d'un parcours en largeur de gauche a droite. L'element

en positionia son ls gauche en position 2iet son ls droit en position 2i+1. On noteparent(i) =bi2 c. SoitT:taille le nombre d'elements dans le tasT. Les feuilles de l'arbre se trouvent entre les indicesbT:taille2 c+ 1 etT:taille.

3 Denition d'un tas binaire

Denition 4 (tas)Un tas est un arbre binaire presque complet ou chaque nud a une valeur plus prioritaire que celle de ses ls.Exemple 5 (tas-max) 41
25

141021

2Exemple 6 (tas-min)

3 11

149921

42

4 Operations

pre :Test un tas post :Test un tas contenant les m^eme elements queTinitialaveceen plus procedureenler(T;e)T:taille:=T:taille+ 1

T[T:taille] :=e

remonter(T;T:taille)pre:Test un tas sauf enT[i] qui est eventuellement trop grand post :Test un tas contenant les m^eme elements queTinitial procedureremonter(T;i)sii >1alorsj:=parent(i) siT[i] strictement plus prioritaire queT[j]alorsechangerT[i] etT[j] remonter(T;j)Exemple 7Enler 51 :41 25

141021

241
25

141021

25141
25

141051

22151
25

141041

221
La complexite de remonter est enO(h) =O(ln(n)) et celle de enler est donc enO(ln(n)).

Remarque 8La fonction remonter est recursive terminale. On peut en ecrire une version sans avoir a simuler une

pile d'appel. 2 pre :Un tasTnon vide post : l'element max deT eet de bord :Tcontient les m^eme elements sauf l'element le plus prioritaire fonctiondeler(T)max :=T[1]

T[1] :=T[T.taille]

T.taille:=T.taille1

tasser(T;1) retournermaxpre : Un tableauTet un indiceiouTest presque un tas sauf enT[i] eet de bord :Tcontient les m^eme elements mais est un tas proceduretasser(T;i)i prio:= indicej2 fi;2i;2i+ 1g \ f1;:::;T:tailleg avecT[j] le plus prioritaire siiprio6=ialorsechangerT[i] etT[iprio] tasser(T;iprio)Exemple 9 51
25

141041

22121
25

141041

241
25

141021

2

5 Construire un tas

pre : Un tableauT eet de bord :Tcontient les m^eme elements et est un tas procedureconstruireTas(T)T.taille:=jTj pouri=bjTj2 ca 1fairetasser(T;i)La complexite deconstruiretasest enO(nln(n)). Mais, on peut demontrer mieux : Theoreme 10La complexite deconstruiretasest enO(n). D emonstration.L'entierndesigne le nombre d'elements dans le tas. La hauteurHdu tas estblognc.

Notonsnhle nombre de noeuds de hauteurh.n

H= 1n

H1= 2n

02HLa complexite estC(n) =Pblognc

h:=0nhO(h).

Lemme 11On anhn2

h. D emonstration.nh2Hhn2 h.

On a doncC(n) =O(nPblognc

h:=0h2 h). Le lemme suivant permet de conclure queC(n) =O(n). 3

Lemme 12

P1 h:=0h2 h= 2. D emonstration.Pour toutx <1, on a

ALGO1 { File de priorite et tas binaire

Francois Schwarzentruber

February 18, 2021TableauTableau trieTas binaire

enfilerO(1)O(n)O(logn) defilerO(n)O(1)O(logn)

Avantage des tas :

source d'inspiration pour de bonnes implem (comme tas de Fibonacci) d'une le de priorite tri par tas qui est en place et optimal structure en place, contrairement aux ABR qui implementent le de priorite avec la m^eme complexite

1 Arbre binaire presque complet

Denition 1 (arbre binaire presque complet)Un arbre binaire est ditpresque completsi

tous les niveaux sont complets sauf eventuellement le dernier.Exemple 2Voici un arbre binaire presque complet avec 6 nuds.7

12 25149
41
Proposition 3Un arbre binaire presque complet annuds est de hauteur6log2(n). D emonstration.SoitHla hauteur de l'arbre. Il y a 1 noeuds au niveau 0 (la racine). Il y a 2 noeuds au niveau 1 (les ls de la racine). Il y a au plus 2 `noeuds au niveau`.= 1 = 2 = 2 H111 On a 1+2+:::2H1sur les niveaux 0 aH1 et au moins un noeud sur le niveauH. Donc : 1+2+:::2H1+1n.

Autrement dit, 2

H1 + 1 = 2Hn. En passant au log, on obtient le resultat de la proposition.

2 Implementation d'un arbre binaire presque complet avec un tableau

Le tableau contient les elements d'indice croissant dans l'ordre d'un parcours en largeur de gauche a droite. L'element

en positionia son ls gauche en position 2iet son ls droit en position 2i+1. On noteparent(i) =bi2 c. SoitT:taille le nombre d'elements dans le tasT. Les feuilles de l'arbre se trouvent entre les indicesbT:taille2 c+ 1 etT:taille.

3 Denition d'un tas binaire

Denition 4 (tas)Un tas est un arbre binaire presque complet ou chaque nud a une valeur plus prioritaire que celle de ses ls.Exemple 5 (tas-max) 41
25

141021

2Exemple 6 (tas-min)

3 11

149921

42

4 Operations

pre :Test un tas post :Test un tas contenant les m^eme elements queTinitialaveceen plus procedureenler(T;e)T:taille:=T:taille+ 1

T[T:taille] :=e

remonter(T;T:taille)pre:Test un tas sauf enT[i] qui est eventuellement trop grand post :Test un tas contenant les m^eme elements queTinitial procedureremonter(T;i)sii >1alorsj:=parent(i) siT[i] strictement plus prioritaire queT[j]alorsechangerT[i] etT[j] remonter(T;j)Exemple 7Enler 51 :41 25

141021

241
25

141021

25141
25

141051

22151
25

141041

221
La complexite de remonter est enO(h) =O(ln(n)) et celle de enler est donc enO(ln(n)).

Remarque 8La fonction remonter est recursive terminale. On peut en ecrire une version sans avoir a simuler une

pile d'appel. 2 pre :Un tasTnon vide post : l'element max deT eet de bord :Tcontient les m^eme elements sauf l'element le plus prioritaire fonctiondeler(T)max :=T[1]

T[1] :=T[T.taille]

T.taille:=T.taille1

tasser(T;1) retournermaxpre : Un tableauTet un indiceiouTest presque un tas sauf enT[i] eet de bord :Tcontient les m^eme elements mais est un tas proceduretasser(T;i)i prio:= indicej2 fi;2i;2i+ 1g \ f1;:::;T:tailleg avecT[j] le plus prioritaire siiprio6=ialorsechangerT[i] etT[iprio] tasser(T;iprio)Exemple 9 51
25

141041

22121
25

141041

241
25

141021

2

5 Construire un tas

pre : Un tableauT eet de bord :Tcontient les m^eme elements et est un tas procedureconstruireTas(T)T.taille:=jTj pouri=bjTj2 ca 1fairetasser(T;i)La complexite deconstruiretasest enO(nln(n)). Mais, on peut demontrer mieux : Theoreme 10La complexite deconstruiretasest enO(n). D emonstration.L'entierndesigne le nombre d'elements dans le tas. La hauteurHdu tas estblognc.

Notonsnhle nombre de noeuds de hauteurh.n

H= 1n

H1= 2n

02HLa complexite estC(n) =Pblognc

h:=0nhO(h).

Lemme 11On anhn2

h. D emonstration.nh2Hhn2 h.

On a doncC(n) =O(nPblognc

h:=0h2 h). Le lemme suivant permet de conclure queC(n) =O(n). 3

Lemme 12

P1 h:=0h2 h= 2. D emonstration.Pour toutx <1, on a