Structure de données - Tas
Un tas est une structure spéciale d'arbre binaire complet qui satisfait la propriété d'ordre du tas. Un tas garantit uniquement la relation de taille entre les nœuds parents et enfants, et n'exige pas d'ordre strict entre les sous-arbres gauche et droit.
Définition et stockage d'un tas
Vue arborescente (tas max)
Vue du tableau (Stockage compact)
Parent : (i-1)/2 | Enfant gauche : 2i+1 | Enfant droit : 2i+2
Arbre binaire complet → naturellement adapté aux tableaux, aucun surcoût de pointeur
Remontée (Insertion) O(log n)
Placer le nouvel élément à la fin → comparer avec le parent → échanger s'il est plus grand → répéter jusqu'au sommet du tas
Descente (Suppression de la racine) O(log n)
Déplacer le dernier élément vers la racine → comparer avec l'enfant le plus grand → échanger s'il est plus petit → répéter jusqu'à une feuille
Deux types de tas :
- Tas maxChaque nœud parent ≥ nœud enfant, le nœud racine est la valeur maximale
- Tas minChaque nœud parent ≤ nœud enfant, le nœud racine est la valeur minimale
Comme un tas est un arbre binaire complet, il est naturellement adapté au stockage en tableau :
| Nœud (indice i) | Relation | Position (base 0) |
|---|---|---|
| Nœud parent | parent(i) | (i - 1) / 2 |
| Nœud enfant gauche | left(i) | 2 * i + 1 |
| Nœud enfant droit | right(i) | 2 * i + 2 |
Insertion et suppression dans un tas (processus Heapify)
Exemple
#define MAX 100
/* Structure de tas max */
struct MaxHeap {
int arr[MAX];
int size; /* Nombre actuel d'éléments */
};
void initHeap(struct MaxHeap* h) { h->size = 0; }
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
/* Remontée : ajuster l'élément nouvellement inséré du bas vers le haut
Comparer avec le nœud parent ; si supérieur au parent, échanger ; répéter jusqu'à ce que l'ordre du tas soit respecté */
void siftUp(struct MaxHeap* h, int idx) {
while (idx > 0) {
int parent = (idx - 1) / 2;
if (h->arr[idx] <= h->arr[parent]) break;
swap(&h->arr[idx], &h->arr[parent]);
idx = parent;
}
}
/* Insertion : placer d'abord l'élément à la fin, puis ajuster avec sift-up O(log n) */
void insert(struct MaxHeap* h, int value) {
if (h->size >= MAX) return;
h->arr[h->size] = value;
siftUp(h, h->size);
h->size++;
}
/* Sift Down : ajuster depuis la racine vers le bas
Comparer avec le plus grand nœud enfant ; si plus petit, échanger ; répéter jusqu'à ce que l'ordre du tas soit satisfait */
void siftDown(struct MaxHeap* h, int idx) {
while (1) {
int largest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < h->size && h->arr[left] > h->arr[largest])
largest = left;
if (right < h->size && h->arr[right] > h->arr[largest])
largest = right;
if (largest == idx) break;
swap(&h->arr[idx], &h->arr[largest]);
idx = largest;
}
}
/* Supprimer la racine (valeur maximale) : déplacer le dernier élément vers le haut, puis ajuster à l'aide de sift-down O(log n) */
int extractMax(struct MaxHeap* h) {
if (h->size == 0) return -1;
int maxVal = h->arr[0];
h->arr[0] = h->arr[--h->size]; /* Déplacer le dernier élément vers le haut */
siftDown(h, 0); /* Ajustement par sift-down */
return maxVal;
}
int main() {
struct MaxHeap h;
initHeap(&h);
int vals[] = {3, 10, 5, 8, 2, 15};
for (int i = 0; i < 6; i++) insert(&h, vals[i]);
printf("Extraire les valeurs maximales dans l'ordre : ");
while (h.size > 0) {
printf("%d ", extractMax(&h));
}
printf("\n"); /* Sortie : 15 10 8 5 3 2 (ordre décroissant) */
return 0;
}
Scénarios d'application
| Scénario | Description |
|---|---|
| File de priorité | Le tas est l'implémentation sous-jacente la plus courante d'une file de priorité |
| Tri par tas | Algorithme de tri en place en O(n log n) (détaillé au chapitre 18) |
| Problème des K plus grands | Utiliser un tas min pour maintenir les K plus grands éléments |