tri en tas

Tri par tas

Le tri par tas est un algorithme de tri conçu en utilisant la structure de données d'un tri par tas est un tri par sélection, son pire et son meilleur, la complexité temporelle moyenne est O. (nlogn), qui est également un tri instable. Tout d’abord, comprenons brièvement la structure du tas.

Tas

Un tas est un arbre binaire complet avec les propriétés suivantes : la valeur de chaque nœud est supérieure ou égale à ses enfants gauche et droit La valeur d'un nœud est appelée un grand tas supérieur ; ou la valeur de chaque nœud est inférieure ou égale à la valeur de ses nœuds enfants gauche et droit, qui est appelé un petit tas supérieur.

Cours recommandé : Tutoriel PHP.

Comme indiqué ci-dessous :

En même temps, nous numérotons les nœuds du tas par couche pour cartographier cette structure logique Cela ressemble à ceci dans le tableau

Le tableau est logiquement une structure de tas Nous utilisons une formule simple pour décrire la définition d'un tas :

Grand. tas supérieur : arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

Petit tas supérieur : arr[i]

L'idée de base du tri par tas est :

Construire la séquence à trié Il forme un grand tas supérieur. À ce stade, la valeur maximale de la séquence entière est le nœud racine en haut du tas. Échangez-le avec le dernier élément, la dernière valeur est alors la valeur maximale. Reconstruisez ensuite les n-1 éléments restants en un tas, de sorte que la plus petite valeur suivante de n éléments soit obtenue. Si vous exécutez ceci à plusieurs reprises, vous obtiendrez une séquence ordonnée

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!