Programmer en TypeScript avec ChatGPT, troisième épisode

Article mis en ligne le 20 octobre 2025

dernière modification le 24 octobre 2025

par Laurent Bloch

Cet article a un prédécesseur et un successeur.

Sommaire

La question
La réponse
Version corrigée complète

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;
    }
}

Cet article a un prédécesseur et un successeur.

Votre inscription a été enregistrée avec succès !