La question
Bonsoir, j’ai écrit une classe TypeScript de tri par tas (HeapSort) qui marche presque mais pas tout à fait, peux-tu y jeter un coup d’œil ?
export class TriTas
{
public trier (V: number[]) {
let T: number[] = [undefined];
for (let i = 0; i < V.length; i++) {
this.augmenter(T, V[i]);
}
for (let i = 0; i < V.length; i++) {
V[V.length -1 -i] = this.extraire(T);
}
console.log('trier, V : ', V);
console.log('trier, T : ', T);
}
private augmenter(T: number[], v: number) {
T.push(v);
let i = T.length - 1;
while (i > 0 && T[i] > T[this.pere(i)]) {
this.permute (T, i, this.pere(i));
i = this.pere(i);
}
console.log('augmenter, T : ', T);
}
private extraire(T: number[]) {
let v = T[1];
this.inserer(T, T.pop());
return v;
}
private inserer(T: number[],
v: number) {
T[1] = v;
let i = 1;
while ((this.fils_gauche(i) < T.length && T[this.fils_gauche(i)] > T[i])
|| (this.fils_droit(i) < T.length && T[this.fils_droit(i)] > T[i])) {
if (this.fils_droit(i) > T.length || T[this.fils_droit(i)] < T[this.fils_gauche(i)]) {
this.permute(T, this.fils_gauche(i), i);
} else {
this.permute(T, this.fils_droit(i), i);
}
}
console.log('inserer T : ', T);
return T;
}
private pere (i: number) {
return Math.floor(i/2);
}
private fils_gauche (i: number) {
return (i * 2);
}
private fils_droit (i: number) {
return ((i * 2) + 1);
}
private permute (V: number[],
i: number,
j: number) {
let tmp: number = V[i];
V[i] = V[j];
V[j] = tmp;
return (V);
}
}import { TriTas } from "./tri_par_tas.js";
let trierTas = new TriTas;
let W = [100, 10, 8, 56, 78, 4, 67, 34];
console.log('main : ', W);
trierTas.trier(W);
console.log('main, W : ', W);La réponse
Ton code est très proche d’un tri par tas correct, mais il contient quelques erreurs subtiles de logique, notamment :
– un index de base incorrect (0 vs 1),
– une remontée/descente incomplète dans le tas,
– et un mauvais cas limite dans extraire et inserer.
Voyons ça point par point.
Indexation du tableau T
Tu démarres le tableau du tas avec :
let T: number[] = [undefined];→ bonne idée pour que la racine soit à T[1].
Mais du coup, tous tes accès doivent supposer que T[0] est inutilisé.
Or dans ta boucle augmenter, tu fais :
while (i > 0 && T[i] > T[this.pere(i)]) {Il faudrait tester i > 1 (sinon this.pere(1) renvoie 0, où il y a undefined).
✅ Corrige :
while (i > 1 && T[i] > T[this.pere(i)]) {Extraire
Tu fais :
let v = T[1];
this.inserer(T, T.pop());
return v;Mais T.pop() supprime et renvoie le dernier élément, qui peut être undefined si le tas est vide.
Et tu appelles inserer même si le tas est vide ensuite, ce qui est dangereux.
✅ Corrige ainsi :
private extraire(T: number[]) {
if (T.length <= 1) return undefined;
const v = T[1];
const dernier = T.pop();
if (T.length > 1 && dernier !== undefined) {
T[1] = dernier;
this.tasser(T, 1);
}
return v;
}Inserer ne tasse pas correctement
Ta méthode inserer mélange la logique de remplacement racine et de heapify down,
mais ta condition :
if (this.fils_droit(i) > T.length || T[this.fils_droit(i)] < T[this.fils_gauche(i)])a une erreur : tu testes > au lieu de >= et tu ne mets jamais à jour i après permutation.
✅ Il faut réécrire la descente correctement :
private tasser(T: number[], i: number) {
while (true) {
const g = this.fils_gauche(i);
const d = this.fils_droit(i);
let plusGrand = i;
if (g < T.length && T[g] > T[plusGrand]) plusGrand = g;
if (d < T.length && T[d] > T[plusGrand]) plusGrand = d;
if (plusGrand === i) break;
this.permute(T, i, plusGrand);
i = plusGrand;
}
}Version corrigée complète
export class TriTas {
public trier(V: number[]) {
const T: (number | undefined)[] = [undefined];
for (const v of V) this.augmenter(T, v);
for (let i = V.length - 1; i >= 0; i--) {
V[i] = this.extraire(T)!;
}
console.log('trier, V : ', V);
console.log('trier, T : ', T);
}
private augmenter(T: (number | undefined)[], v: number) {
T.push(v);
let i = T.length - 1;
while (i > 1 && T[i]! > T[this.pere(i)]!) {
this.permute(T, i, this.pere(i));
i = this.pere(i);
}
console.log('augmenter, T : ', T);
}
private extraire(T: (number | undefined)[]) {
if (T.length <= 1) return undefined;
const v = T[1]!;
const dernier = T.pop();
if (T.length > 1 && dernier !== undefined) {
T[1] = dernier;
this.tasser(T, 1);
}
return v;
}
private tasser(T: (number | undefined)[], i: number) {
while (true) {
const g = this.fils_gauche(i);
const d = this.fils_droit(i);
let plusGrand = i;
if (g < T.length && T[g]! > T[plusGrand]!) plusGrand = g;
if (d < T.length && T[d]! > T[plusGrand]!) plusGrand = d;
if (plusGrand === i) break;
this.permute(T, i, plusGrand);
i = plusGrand;
}
console.log('tasser, T : ', T);
}
private pere(i: number) { return Math.floor(i / 2); }
private fils_gauche(i: number) { return 2 * i; }
private fils_droit(i: number) { return 2 * i + 1; }
private permute(V: (number | undefined)[], i: number, j: number) {
const tmp = V[i];
V[i] = V[j];
V[j] = tmp;
}
}