Partage de technologie

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

tas

Tas et file d'attente prioritaire :

La file d'attente prioritaire est un type de données abstrait et le tas est une structure de données, donc le tas n'est pas une file d'attente prioritaire. Le tas est un moyen d'implémenter une file d'attente prioritaire.
Il existe de nombreuses façons d'implémenter des files d'attente prioritaires, telles que des tableaux et des listes chaînées. Cependant, ces implémentations ne peuvent garantir que l'une des opérations d'insertion et de suppression peut être effectuée dans une complexité temporelle O(1)O(1), tandis que l'autre opération doit être effectuée dans O(N)O(N) Terminé dans le délai de complexité temporelle O(1)O(1). complexité temporelle. Le tas peut permettre à l'opération d'insertion de la file d'attente prioritaire d'être terminée dans la complexité temporelle de O(log N)O(logN), et à l'opération de suppression d'être terminée dans la complexité temporelle de O(log N)O(logN) .

Un tas est un arbre binaire spécial qui remplit les conditions suivantes :

1. Arbre binaire complet (les nœuds sont placés dans l'ordre de gauche à droite) ;
2. La valeur de chaque nœud doit être supérieure ou égale ou inférieure ou égale à la valeur de son nœud enfant.

Caractéristiques du tas :

1. Les éléments peuvent être insérés dans le tas avec une complexité temporelle O(logN) ;
2. Les éléments peuvent être supprimés du tas en complexité temporelle O(logN) ;
3. La valeur maximale ou minimale dans le tas peut être obtenue dans une complexité temporelle O(1).

Classification des tas :

Tas maximum : la valeur de chaque nœud dans le tas est supérieure ou égale à la valeur de son nœud enfant. L'élément supérieur (nœud racine) du tas max est la valeur maximale du tas.
Tas minimum : la valeur de chaque nœud dans le tas est inférieure ou égale à la valeur de son nœud enfant. L'élément supérieur (nœud racine) d'un min-heap est la valeur minimale du tas.
Le numéro de nœud actuel est i, le numéro de l'enfant de gauche est 2i et le numéro de l'enfant de droite est 2i+1.

Complexité temporelle et complexité spatiale

Tri en tas

Théorie : le tri par tas fait référence à l'utilisation de la structure de données du tas pour trier un ensemble d'éléments non ordonnés.

Les étapes de l'algorithme de tri min-heap sont les suivantes :

Regroupez tous les éléments dans un tas minimum ;
Retirez et supprimez l'élément supérieur du tas, et placez l'élément supérieur du tas dans l'ensemble de données T qui stocke les éléments ordonnés ;
À ce moment-là, le tas sera ajusté au nouveau tas minimum ;
Répétez les étapes 3 et 4 jusqu'à ce qu'il n'y ait plus d'éléments dans le tas ;
À ce stade, un nouvel ensemble de données T est obtenu, dans lequel les éléments sont classés du plus petit au plus grand.

Les étapes de l'algorithme de tri du tas maximum sont les suivantes :

Regroupez tous les éléments dans un tas maximum ;
Retirez et supprimez l'élément supérieur du tas, et placez l'élément supérieur du tas dans l'ensemble de données T qui stocke les éléments ordonnés ;
À ce moment-là, le tas sera ajusté au nouveau tas maximum ;
Répétez les étapes 3 et 4 jusqu'à ce qu'il n'y ait plus d'éléments dans le tas ;
À ce stade, un nouvel ensemble de données T est obtenu, dans lequel les éléments sont classés du plus grand au plus petit.
Complexité temporelle : O(Nlog N). N est le nombre d'éléments dans le tas.

Complexité spatiale : O(N). N est le nombre d'éléments dans le tas.