Le tas binaire (Binary Heap) est une structure de données fondmaentale permettant de maintenir un ensemble d'éléments et d'accéder rapidement à l'élément minimal ou maximal. Dans le cas d'un tas-min (min-heap), la racine contient toujours la plus petite valeur.

1. Implémentation manuelle d'un tas-min

Un tas binaire peut être représenté efficacement sous forme de tableau. Pour un élément situé à l'indice i, son enfant gauche se trouve à 2*i et son enfant droit à 2*i + 1. Son parent se situe à i/2.

Insertion (Up-heap)

Pour ajouter un élément, on le place à la fin du tableau, puis on le fait "remonter" tant qu'il est plus petit que son parent.

int arbre[1000001];
int total_elements = 0;

void inserer(int valeur) {
    arbre[++total_elements] = valeur;
    int actuel = total_elements;
    while (actuel > 1) {
        int parent = actuel / 2;
        if (arbre[actuel] < arbre[parent]) {
            int temp = arbre[actuel];
            arbre[actuel] = arbre[parent];
            arbre[parent] = temp;
            actuel = parent;
        } else {
            break;
        }
    }
}

Suppression de la racine (Down-heap)

Pour supprimer l'élément minimal, on remplace la racine par le dernier élément du tableau, on réduit la taille, puis on fait "descendre" cette nouvelle racine pour restaurer la propriété du tas.

void supprimer_min() {
    if (total_elements == 0) return;
    arbre[1] = arbre[total_elements--];
    int actuel = 1;
    while (actuel * 2 <= total_elements) {
        int enfant = actuel * 2;
        // Choisir l'enfant le plus petit
        if (enfant + 1 <= total_elements && arbre[enfant + 1] < arbre[enfant]) {
            enfant++;
        }
        if (arbre[actuel] > arbre[enfant]) {
            int temp = arbre[actuel];
            arbre[actuel] = arbre[enfant];
            arbre[enfant] = temp;
            actuel = enfant;
        } else {
            break;
        }
    }
}

2. Utilisation de la bibliothèque standard (STL)

En C++, la classe std::priority_queue de la bibliothèque <queue> permet de manipuler un tas sans implémentation manuelle. Par défaut, il s'agit d'un tas-max. Pour obtenir un tas-min, on utilise le comparateur std::greater.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    // Déclaration d'un tas-min
    priority_queue<int, vector<int>, greater<int>> file_priorite;
    
    int n;
    if (!(cin >> n)) return 0;
    
    while (n--) {
        int type_op;
        cin >> type_op;
        if (type_op == 1) {
            int val;
            cin >> val;
            file_priorite.push(val);
        } else if (type_op == 2) {
            cout << file_priorite.top() << "\n";
        } else if (type_op == 3) {
            if (!file_priorite.empty()) {
                file_priorite.pop();
            }
        }
    }
    return 0;
}

3. Fonctions algorithmiques de la STL

Il est également possible d'utiliser les fonctions std::push_heap et std::pop_heap sur un conteneur existant (comme un std::vector ou un tableau classique) pour lui donner un comportement de tas.

#include <algorithm>
#include <vector>

// Pour ajouter un élément :
conteneur.push_back(valeur);
push_heap(conteneur.begin(), conteneur.end(), greater<int>());

// Pour supprimer l'élément minimal :
pop_heap(conteneur.begin(), conteneur.end(), greater<int>());
conteneur.pop_back();

Le choix entre l'implémentation manuelle et la STL dépend des contraintes de performance spécifiques et de la nécessité ou non de modifier la structure interne du tas (par exemple, pour modifier une valeur arbitraire dans le tas, une implémentation manuelle est souvent requise).