UN Tas est un spécial arbre binaire complet . Puisqu’un tas est un arbre binaire complet, un tas avec N les nœuds ont journal N hauteur. Il est utile de supprimer l’élément de priorité la plus élevée ou la plus basse. Il est généralement représenté comme un tableau . Il existe deux types de tas dans leMin-Tas
Dans un Min-Tas la clé présente au nœud racine doit être inférieure ou égale parmi les clés présentes chez tous ses enfants. La même propriété doit être vraie de manière récursive pour tous les sous-arbres de cet arbre binaire. Dans un Min-Heap, l'élément clé minimum présent à la racine. Vous trouverez ci-dessous l'arbre binaire qui satisfait toutes les propriétés de Min Heap.
Tas maximum
Dans un Tas maximum la clé présente au nœud racine doit être supérieure ou égale parmi les clés présentes chez tous ses enfants. La même propriété doit être récursivement vrai pour tous les sous-arbres de cet arbre binaire. Dans un Max-Heap, l'élément clé maximum présent à la racine. Vous trouverez ci-dessous l'arbre binaire qui satisfait toutes les propriétés de Max Heap.
Différence entre le tas minimum et le tas maximum
| Tas minimum | Tas maximum | |
|---|---|---|
| 1. | Dans un Min-Heap, la clé présente sur le nœud racine doit être inférieure ou égale à parmi les clés présentes sur tous ses enfants. | Dans un Max-Heap, la clé présente sur le nœud racine doit être supérieure ou égale à parmi les clés présentes sur tous ses enfants. |
| 2. | Dans un Min-Heap, l'élément clé minimum présent à la racine. | Dans un Max-Heap, l'élément clé maximum présent à la racine. |
| 3. | Un Min-Heap utilise la priorité croissante. | Un Max-Heap utilise la priorité décroissante. |
| 4. | Dans la construction d’un Min-Heap, le plus petit élément est prioritaire. | Dans la construction d’un Max-Heap, le plus gros élément est prioritaire. |
| 5. | Dans un Min-Heap, le plus petit élément est le premier à être extrait du tas. | Dans un Max-Heap, le plus grand élément est le premier à être extrait du tas. |
Applications des tas :
- Tri en tas : Heap Sort est l'un des meilleurs algorithmes de tri utilisant Tas binaire à trier un tableau dans O(N*logN) temps.
- File d'attente de priorité : Une file d'attente prioritaire peut être implémentée en utilisant un tas car elle prend en charge insérer() , supprimer() , extraireMax() , diminuerKey() opérations dans O (log N) temps.
- Le chemin le plus court de Dijkstra et Arbre couvrant minimum de Prim .
Analyse des performances de Min-Heap et Max-Heap :
- Obtenir l'élément maximum ou minimum : O(1)
- Insérer un élément dans Max-Heap ou Min-Heap : O (log N)
- Supprimer l'élément maximum ou minimum : O (log N)