Quel type de tri est le tri en tas ?

Le tri par tas est une méthode permettant de générer un tas maximum à partir d'une séquence non ordonnée, d'échanger les positions de l'élément supérieur du tas avec le dernier élément et de générer un tas maximum avec les éléments restants. séquentiellement pour générer un tri maximal.

Tri par tas

Générez une séquence non ordonnée dans un tas maximum et combinez l'élément supérieur de le tas avec Le dernier élément échange ses positions, et les éléments restants sont générés pour générer un tas maximum Les éléments sont échangés séquentiellement et un tas maximum est généré

Complexité temporelle : O(NlogN) Complexité spatiale : O( 1)

Introduction :

Le tri par tas (anglais : Heapsort) fait référence à un algorithme de tri conçu en utilisant la structure de données d'un tas. Un tas est une structure qui se rapproche d'un arbre binaire complet et satisfait en même temps à la propriété de tas : c'est-à-dire que la valeur clé ou l'index d'un nœud enfant est toujours plus petit (ou plus grand) que son nœud parent.

Opérations sur le tas

Dans la structure de données du tas, la valeur maximale dans le tas est toujours située au nœud racine (si le tas est utilisé dans une file d'attente prioritaire, la valeur minimale dans le tas est situé au niveau du nœud racine).

Les opérations suivantes sont définies dans le tas :

Max Heapify : Ajustez le nœud enfant final du tas pour que le nœud enfant soit toujours plus petit que le nœud parent

Build Max Heap : réorganisez toutes les données dans le tas

HeapSort : supprimez le nœud racine des premières données et effectuez l'opération récursive d'ajustement max du tas

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!