Tas (tas binaire)
Dernière mise à jour
Un tas binaire est un arbre binaire complet qui garde la plus petite valeur (min-heap) ou la plus grande (max-heap) à la racine. Cette visualisation est un min-heap : chaque parent est inférieur ou égal à ses enfants. Pour ajouter une valeur, on l'ajoute à la prochaine position libre, puis on la "fait remonter" en l'échangeant avec son parent tant qu'elle est plus petite, jusqu'à ce que la propriété de tas soit rétablie. Appuyez sur lecture ci-dessus pour voir chaque nouvelle valeur remonter jusqu'à sa place.
Comme un tas est un arbre complet, il est stocké de façon compacte dans un tableau : les enfants du nœud i sont en 2i+1 et 2i+2. L'insertion et la suppression du minimum sont en O(log n) (un chemin de la racine à une feuille), tandis que consulter le minimum est en O(1) - exactement ce dont une file de priorité a besoin.
Complexité en temps et en espace
| Opération | Complexité | Remarques |
|---|---|---|
| Consulter min/max | O(1) | C'est toujours la racine |
| Insérer (push) | O(log n) | Remonter le long d'un chemin |
| Supprimer min/max | O(log n) | Descendre le long d'un chemin |
| Construire le tas | O(n) | Heapify en une seule fois |
| Espace | O(n) | Basé sur un tableau, sans pointeurs |
Étape par étape (push)
| Étape | Ce qui se passe |
|---|---|
| 1 | Ajoutez la nouvelle valeur à la fin (la prochaine feuille libre). |
| 2 | Comparez-la à son parent. |
| 3 | Si elle est plus petite (min-heap), échangez-la vers le haut. |
| 4 | Répétez jusqu'à ce qu'elle ne soit plus plus petite que son parent ou atteigne la racine. |
Exemple résolu
Construction d'un min-heap en insérant [5, 3, 8, 1, 4] une valeur à la fois :
| Push | Tableau après remontée | Action |
|---|---|---|
5 | [5] | La première valeur devient la racine. |
3 | [3, 5] | 3 < parent 5, donc elle remonte jusqu'à la racine. |
8 | [3, 5, 8] | 8 > parent 5, donc elle reste une feuille. |
1 | [1, 3, 8, 5] | 1 < parent 5, échange ; puis 1 < parent 3, remonte jusqu'à la racine. |
4 | [1, 3, 8, 5, 4] | 4 > parent 3, donc elle reste ; le minimum 1 demeure à la racine. |
Quand utiliser un tas
| Utilisez-le quand | Évitez-le quand |
|---|---|
| Vous avez régulièrement besoin du plus petit ou du plus grand élément d'un ensemble changeant. | Vous devez rechercher des valeurs arbitraires, pas seulement l'extrême - utilisez un BST ou un ensemble de hachage. |
| Vous implémentez une file de priorité pour Dijkstra, A* ou un ordonnanceur. | Vous devez garder les données entièrement triées en permanence. |
Vous voulez une insertion et une suppression du minimum en O(log n) avec une disposition en tableau compacte. | Vous avez besoin d'une recherche ou d'une suppression rapide d'un élément précis (non racine). |
| Vous devez fusionner un flux d'éléments et les extraire par priorité. | L'ensemble de données est minuscule et un parcours linéaire est plus simple et assez rapide. |
Code de Heap (Priority Queue)
Une implémentation propre et exécutable de Heap (Priority Queue) en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Heap (Priority Queue) en Python
Python
1class MinHeap:2 def __init__(self):3 self.data = []4
5 def push(self, value):6 # Append at the end, then bubble up to restore order7 self.data.append(value)8 i = len(self.data) - 19 while i > 0:10 parent = (i - 1) // 211 if self.data[parent] <= self.data[i]:12 break13 self.data[i], self.data[parent] = self.data[parent], self.data[i]14 i = parent15
16 def pop(self):17 # Move the last leaf to the root, then sift it down18 top = self.data[0]19 last = self.data.pop()20 if self.data:21 self.data[0] = last22 self._sift_down(0)23 return top24
25 def _sift_down(self, i):26 n = len(self.data)27 while True:28 smallest = i29 left, right = 2 * i + 1, 2 * i + 230 if left < n and self.data[left] < self.data[smallest]:31 smallest = left32 if right < n and self.data[right] < self.data[smallest]:33 smallest = right34 if smallest == i:35 return36 self.data[i], self.data[smallest] = self.data[smallest], self.data[i]37 i = smallest38
39
40heap = MinHeap()41for value in [5, 3, 8, 1, 9, 2]:42 heap.push(value)43
44print("Heap array: ", heap.data)45print("Popped in order:", [heap.pop() for _ in range(6)])Code de Heap (Priority Queue) en JavaScript
JavaScript
1class MinHeap {2 constructor() {3 this.items = [];4 }5
6 push(value) {7 this.items.push(value);8 // Bubble the new value up while it is smaller than its parent9 let i = this.items.length - 1;10 while (i > 0) {11 const parent = Math.floor((i - 1) / 2);12 if (this.items[parent] <= this.items[i]) break;13 [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];14 i = parent;15 }16 }17
18 pop() {19 const top = this.items[0];20 const last = this.items.pop();21 if (this.items.length > 0) {22 this.items[0] = last;23 this.sinkDown(0);24 }25 return top;26 }27
28 sinkDown(i) {29 const n = this.items.length;30 while (true) {31 let smallest = i;32 const left = 2 * i + 1;33 const right = 2 * i + 2;34 if (left < n && this.items[left] < this.items[smallest]) smallest = left;35 if (right < n && this.items[right] < this.items[smallest]) smallest = right;36 if (smallest === i) return;37 [this.items[i], this.items[smallest]] = [this.items[smallest], this.items[i]];38 i = smallest;39 }40 }41}42
43const heap = new MinHeap();44for (const value of [5, 2, 9, 1, 7, 3]) heap.push(value);45const sorted = [];46while (heap.items.length > 0) sorted.push(heap.pop());47console.log("Popped in order:", sorted.join(" "));Code de Heap (Priority Queue) en Java
Java
1public class Main {2 static int[] heap = new int[32];3 static int size = 0;4
5 static void push(int value) {6 heap[size] = value;7 int i = size++;8 // Sift up while smaller than the parent9 while (i > 0 && heap[(i - 1) / 2] > heap[i]) {10 swap(i, (i - 1) / 2);11 i = (i - 1) / 2;12 }13 }14
15 static int pop() {16 int min = heap[0];17 heap[0] = heap[--size];18 int i = 0;19 // Sift down: swap with the smaller child until in place20 while (true) {21 int smallest = i, l = 2 * i + 1, r = 2 * i + 2;22 if (l < size && heap[l] < heap[smallest]) smallest = l;23 if (r < size && heap[r] < heap[smallest]) smallest = r;24 if (smallest == i) break;25 swap(i, smallest);26 i = smallest;27 }28 return min;29 }30
31 static void swap(int a, int b) {32 int tmp = heap[a];33 heap[a] = heap[b];34 heap[b] = tmp;35 }36
37 public static void main(String[] args) {38 int[] values = {9, 4, 7, 1, 8, 2};39 for (int v : values) push(v);40 System.out.print("Popped in order:");41 while (size > 0) System.out.print(" " + pop());42 System.out.println();43 }44}Code de Heap (Priority Queue) en C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5struct MinHeap {6 std::vector<int> data;7
8 void push(int value) {9 data.push_back(value);10 // Sift up until the parent is no larger11 size_t i = data.size() - 1;12 while (i > 0) {13 size_t parent = (i - 1) / 2;14 if (data[parent] <= data[i]) break;15 std::swap(data[parent], data[i]);16 i = parent;17 }18 }19
20 int pop() {21 int top = data[0];22 data[0] = data.back();23 data.pop_back();24 // Sift down: swap with the smaller child25 size_t i = 0;26 while (true) {27 size_t l = 2 * i + 1, r = 2 * i + 2, smallest = i;28 if (l < data.size() && data[l] < data[smallest]) smallest = l;29 if (r < data.size() && data[r] < data[smallest]) smallest = r;30 if (smallest == i) break;31 std::swap(data[i], data[smallest]);32 i = smallest;33 }34 return top;35 }36
37 int peek() const { return data[0]; }38 bool empty() const { return data.empty(); }39};40
41int main() {42 MinHeap heap;43 for (int value : {5, 3, 8, 1, 9, 2}) heap.push(value);44 std::cout << "Min: " << heap.peek() << "\n";45 std::cout << "Popped in order: ";46 while (!heap.empty()) std::cout << heap.pop() << " ";47 std::cout << "\n";48 return 0;49}Code de Heap (Priority Queue) en C
C
1#include <stdio.h>2
3#define CAP 644
5int heap[CAP];6int heapSize = 0;7
8void push(int value) {9 // Sift up until the parent is no larger10 int i = heapSize++;11 heap[i] = value;12 while (i > 0) {13 int parent = (i - 1) / 2;14 if (heap[parent] <= heap[i]) break;15 int tmp = heap[parent];16 heap[parent] = heap[i];17 heap[i] = tmp;18 i = parent;19 }20}21
22int pop(void) {23 int top = heap[0];24 heap[0] = heap[--heapSize];25 // Sift down: swap with the smaller child26 int i = 0;27 while (1) {28 int l = 2 * i + 1, r = 2 * i + 2, smallest = i;29 if (l < heapSize && heap[l] < heap[smallest]) smallest = l;30 if (r < heapSize && heap[r] < heap[smallest]) smallest = r;31 if (smallest == i) break;32 int tmp = heap[i];33 heap[i] = heap[smallest];34 heap[smallest] = tmp;35 i = smallest;36 }37 return top;38}39
40int main(void) {41 int values[] = {5, 3, 8, 1, 9, 2};42 for (int i = 0; i < 6; i++) push(values[i]);43 printf("Min: %d\n", heap[0]);44 printf("Popped in order: ");45 while (heapSize > 0) printf("%d ", pop());46 printf("\n");47 return 0;48}FAQ sur les tas
À quoi sert un tas ?
Les tas implémentent des files de priorité, qui alimentent l'algorithme du plus court chemin de Dijkstra, les ordonnanceurs de tâches et les simulations d'événements. Ils sont aussi le moteur du heapsort. Chaque fois que vous avez régulièrement besoin du plus petit ou du plus grand élément d'un ensemble changeant, un tas est l'outil approprié.
Quelle est la différence entre un tas et un arbre binaire de recherche ?
Les deux sont des arbres binaires, mais un BST maintient un ordre complet de gauche à droite (permettant une recherche ordonnée), tandis qu'un tas ne garantit que la relation parent-enfant (min ou max à la racine). Un tas donne un accès O(1) à la valeur extrême ; un BST donne une recherche en O(log n) pour n'importe quelle valeur.
Pourquoi un tas est-il stocké dans un tableau ?
Comme un tas est toujours un arbre binaire complet, ses nœuds se mappent parfaitement sur les indices d'un tableau : les enfants de l'indice
i sont en 2i+1 et 2i+2, et le parent en (i-1)/2. Cela évite de stocker des pointeurs vers les enfants et offre d'excellentes performances de cache.Un tas est-il la même chose qu'un tableau trié ?
Non. Un tas garantit seulement que chaque parent est plus petit (min-heap) ou plus grand (max-heap) que ses enfants, donc les frères et cousins ne sont dans aucun ordre particulier. Un tableau trié est entièrement ordonné mais coûte
O(n) à l'insertion, tandis qu'un tas insère en O(log n) tout en donnant un accès instantané à la valeur extrême.Quand devrais-je utiliser un tas plutôt que simplement trier un tableau ?
Optez pour un tas quand les données changent sans cesse et que vous n'avez besoin que du minimum ou du maximum courant - insérer et extraire coûtent
O(log n) chacun, contre re-trier tout le tableau. Si vous avez un ensemble de données statique et voulez tous les éléments dans l'ordre, un seul tri en O(n log n) est plus simple et souvent plus rapide.Construire un tas à partir de n éléments prend-il O(n log n) ?
Pas si vous le construisez d'un seul coup. Insérer
n éléments un par un est en O(n log n), mais le heapify ascendant, qui descend du dernier parent jusqu'à la racine, s'exécute en O(n) au total, car la plupart des nœuds sont proches du bas et ne descendent que sur une courte distance.Ressources associées
Plus de visualisations
