• Plus efficace qu'une file d'attente standard
• Chaque élément extrait possède la priorité la plus élevée
• Peut être implémentée avec diverses structures de données comme les tableaux ou les listes chaînées, mais la structure de **tas** est la plus courante

Concepsion

L'immplémentaiton repose sur une structure de **tas**, qui utilise un tableau comme structure sous-jacente.

Attributs :

• tas : stocke les éléments de la file

Méthodes :

• ajouter : pour insérer un élément
• retirer : pour extraire un élément
• premier : pour consulter le premier élément
• estVide : pour vérifier si la file est vide
• taille : pour obtenir la longueur de la file

Implémentation du tas

export default class Tas<t> {
  // Tableau pour stocker les éléments du tas
  private elements: T[] = [];

  // Nombre d'éléments dans le tas
  private compteur: number = 0;

  constructor(elements: T[] = []) {
    this.construireTas(elements);
  }

  // Échange deux éléments dans le tableau
  private echanger(i: number, j: number) {
    const temp = this.elements[i];
    this.elements[i] = this.elements[j];
    this.elements[j] = temp;
  }

  // Retourne la taille du tas
  get taille(): number {
    return this.compteur;
  }

  // Retourne la valeur maximale/minimale
  premier(): T | undefined {
    return this.elements[0];
  }

  // Vérifie si le tas est vide
  estVide(): boolean {
    return this.compteur === 0;
  }

  // Insère un nouvel élément
  inserer(valeur: T) {
    // Ajoute le nouvel élément à la fin du tableau
    this.elements.push(valeur);
    this.compteur++;

    this.remonter();
  }

  // Opération de remontée
  remonter() {
    // Indice de l'élément nouvellement inséré
    let indiceActuel = this.compteur - 1;

    // Continue tant qu'on n'atteint pas la racine
    while (indiceActuel > 0) {
      // Calcule l'indice du parent
      let indiceParent = Math.floor((indiceActuel - 1) / 2);

      // Si l'enfant est inférieur ou égal au parent, on arrête
      if (this.elements[indiceActuel] <= this.elements[indiceParent]) {
        break;
      }

      // Échange l'enfant et le parent
      this.echanger(indiceActuel, indiceParent);

      // Met à jour l'indice actuel
      indiceActuel = indiceParent;
    }
  }

  // Extrait le premier élément
  extraire(): T | undefined {
    // 1. Gestion des cas limites
    if (this.compteur === 0) return undefined;
    if (this.compteur === 1) {
      this.compteur--;
      return this.elements.pop();
    }

    // 2. Extrait et retourne la valeur maximale
    const valeurTop = this.elements[0];
    this.elements[0] = this.elements.pop()!;
    this.compteur--;

    // 3. Maintient la propriété du tas : opération de descente
    this.descendre(0);

    return valeurTop;
  }

  // Opération de descente
  debuter(indiceDepart: number) {
    let index = indiceDepart;

    while (2 * index + 1 < this.compteur) {
      let indiceGauche = 2 * index + 1;
      let indiceDroit = 2 * index + 2;
      let plusGrandIndice = indiceGauche;

      if (indiceDroit < this.compteur && this.elements[indiceDroit] > this.elements[indiceGauche]) {
        plusGrandIndice = indiceDroit;
      }

      // Si l'enfant est plus grand que le parent, on échange
      if (this.elements[plusGrandIndice] > this.elements[index]) {
        this.echanger(plusGrandIndice, index);
        index = plusGrandIndice;
      } else {
        break;
      }
    }
  }

  // Construction du tas en place
  construireTas(elements: T[]) {
    this.elements = elements;
    this.compteur = elements.length;

    // Trouve le dernier noeud non-feuille
    const depart = Math.floor((this.compteur - 1) / 2);

    for (let i = depart; i >= 0; i--) {
      this.descendre(i);
    }
  }
}

// Test du tas
const tas = new Tas<number>();

tas.inserer(1);
tas.inserer(4);
tas.inserer(15);

console.log(tas.extraire());
console.log(tas.extraire());

console.log(tas);
</number></t>

Implémentation de la file de priorité basée sur un tas

// Importation de la classe Tas précédente
import Tas from './tas.ts';

class NoeudPriorite<t> {
  valeur: T;
  priorite: number;

  constructor(valeur: T, priorite: number) {
    this.valeur = valeur;
    this.priorite = priorite;
  }

  valeurDe() {
    return this.priorite;
  }
}

class FilePriorite<t> {
  private tas: Tas<noeudpriorite>> = new Tas();

  ajouter(valeur: T, priorite: number) {
    const nouveauNoeud = new NoeudPriorite<t>(valeur, priorite);
    this.tas.inserer(nouveauNoeud);
  }

  retirer(): T | undefined {
    return this.tas.extraire()?.valeur;
  }

  premier(): T | undefined {
    return this.tas.premier()?.valeur;
  }

  estVide() {
    return this.tas.estVide();
  }

  get taille() {
    return this.tas.taille;
  }
}

// Test de la file de priorité
const filePriorite = new FilePriorite<string>();

filePriorite.ajouter('alice', 124);
filePriorite.ajouter('bob', 34);
filePriorite.ajouter('charlie', 38);

console.log(filePriorite.retirer());
console.log(filePriorite.retirer());
console.log(filePriorite.retirer());
</string></t></noeudpriorite></t></t>