1. Connaissances de base
Ce que nous appelons habituellement un tas fait référence à un tas binaire, qui est également appelé arbre binaire complet ou à un arbre binaire approximativement complet. Le tas binaire est divisé en le plus grand tas et le plus petit tas.
Le tri du tas fait référence à un algorithme de tri conçu à l'aide de la structure des données du tas, qui est une sorte de sélection de tri. Vous pouvez rapidement localiser les éléments de l'indice spécifié en utilisant les caractéristiques du tableau. Les tableaux peuvent obtenir directement des éléments basés sur l'indice, et la complexité temporelle est O (1), c'est-à-dire les constantes, de sorte qu'elles sont extrêmement efficaces pour l'acquisition de valeur.
Les caractéristiques du tas maximum sont les suivantes:
Les caractéristiques du tas minimum sont les suivantes:
2. Réflexion sur algorithme
1. L'idée de l'algorithme du plus grand tas est:
Tout d'abord, le R initial [0… n-1] est intégré dans le plus grand tas. À l'heure actuelle, c'est un tas non ordonné. Le haut du tas est le plus grand élément, puis le dernier enregistrement r [n-1] de la zone non ordonnée est échangé. Il en résulte la nouvelle zone non ordonnée r [0… n-2] et la zone ordonnée r [n-1], et satisfaire r [0… n-2]. Clés ≤ r [n-1] .key
Étant donné que le premier r [0… n-2] peut ne pas satisfaire les propriétés du tas maximum après l'échange, le premier r [0… n-2] est ajusté au tas maximum jusqu'à ce que le dernier élément de R [0] soit ajusté.
Une fois le type de tas maximum terminé, il s'agit en fait d'une séquence ascendante. Chaque fois que le tas est ajusté, l'élément le plus grand est obtenu puis échangé avec le dernier élément du tas de courant. Par conséquent, la séquence finale obtenue est une séquence ascendante.
2. L'idée de l'algorithme du plus petit tas est:
Tout d'abord, le R initial [0… n-1] est intégré dans le plus petit tas. À l'heure actuelle, c'est un tas non ordonné. L'élément supérieur du tas est le plus petit élément, puis échange le r [0] supérieur avec le dernier r [n-1] de la zone non ordonnée, obtenant ainsi le nouveau tas non ordonné R [0… n-2] et le tas ordonné r [n-1], et satisfaisant r [0… n-2] .keys> = r [n-1] .key.
Étant donné que le premier r [0… n-2] peut ne pas répondre aux propriétés du tas minimum après l'échange, le premier r [0… n-2] est ajusté au tas minimum jusqu'à ce que le dernier élément de R [0] soit ajusté et que le tas minimum soit trié. Une fois la commande du tas minimum terminée, c'est en fait une séquence descendant. Chaque fois que le tas est ajusté, le plus petit élément est obtenu puis échangé avec le dernier élément du tas de courant non ordonné, de sorte que la séquence obtenue est dans l'ordre descendant.
CONSEIL: Le processus de tri des tas est en fait le processus d'élargissement en continu de la zone ordonnée, puis de réduire en continu la zone désordonnée jusqu'à ce qu'il n'y ait que des zones ordonnées.
3. Analyse du processus de tri
Parce que l'algorithme est relativement abstrait, nous illustrons ici directement le processus de tri des tas en donnant un petit exemple. Ensuite, nous utilisons cette séquence non ordonnée pour utiliser le plus grand tas pour le tri du tas, et la séquence résultante est la séquence ascendante (ASC).
Séquence non ordonnée: 89, -7,999, -89,7,0, -888,7, -7
Étape 1: Initialisez le tas maximum à construire:
Étape 2: Échangez l'élément maximum 999 en haut du tas avec le dernier élément de la zone non ordonnée, de sorte que 999 devient une zone ordonnée. Après l'échange, -7 devient le haut du tas. Étant donné que -7 n'est pas l'élément le plus grand de la zone non ordonnée, il est nécessaire d'ajuster la zone non ordonnée afin que la valeur maximale 89 dans la zone non ordonnée devienne le sommet du tas, donc -7 et 89 sont échangés. Après l'échange, le sous-arbre droit de 89 ne répond pas aux propriétés du plus grand tas, de sorte que le sous-arbre droit doit être ajusté au plus grand tas, donc -7 doit être échangé avec 0, comme indiqué sur la figure ci-dessous:
À partir du chiffre, lorsque -7% 89% d'échange, le haut de la pile est l'élément le plus grand, mais l'enfant gauche de -7 est 0 et l'enfant droit est -888. Depuis -7 <0, le nœud -7 ne répond pas aux propriétés du tas, il doit donc être ajusté. Ainsi, 0 est échangé avec -7.
Répétez ensuite la deuxième étape jusqu'à ce qu'elle devienne une zone ordonnée.
Enfin: ce qui est obtenu est une séquence ascendante
4. Complexité du temps
Le temps du tri du tas est principalement composé de la surcharge de temps d'établissement du tas initial et d'ajuster à plusieurs reprises le tas. Étant donné que le tri du tas est instable, la complexité du temps qu'il obtient sera plus élevée en fonction de la situation réelle, donc elle ne peut prendre que la complexité du temps moyen.
La complexité du temps moyenne est: o (n * log2 (n))
Les opérations longues du tri du tas comprennent: le tas initial + ajustement répété du tas, et la complexité temporelle est la suivante:
1. Bâtiment de tas initial: chaque nœud parent se comparera et échangera avec les nœuds enfants gauche et droit jusqu'à 2 fois, de sorte que la complexité est liée au nombre de nœuds parents. Sur la base de 2x <= n (x est le nombre de fois où les éléments peuvent être pliés en deux, c'est-à-dire le nombre de nœuds parents), il est obtenu x = log2n. C'est-à-dire o (log2n)
2. Réglage répété du tas: Étant donné que les résultats de comparaison du tableau sont enregistrés lors de l'initialisation du tas, le tri du tas n'est pas sensible à l'ordre du tableau de la séquence d'origine, et la meilleure situation est similaire au pire des cas. L'élément supérieur du tas doit être extrait des fois N-1. Chaque fois que l'élément de haut du tas est pris, le tas doit être reconstruit (o (reconstruire le tas) <o (tas initial)). Donc moins de o (n-1) * o (log2n)
Utilisation recommandée:
Étant donné que le nombre de fois que l'initialisation du tas doit être comparée, le tri du tas est plus adapté aux situations où la quantité de données est très grande (millions de données ou plus). Étant donné que le tri rapide efficace est basé sur l'implémentation récursive, une erreur de débordement de pile se produit lorsque le volume de données est très important.
5. Exemple de code Java
classe publique Heapsort {private static int [] tri = new int [] {1,0,10,20,3,5,6,4,9,8,12, 17,34,11}; public static void main (String [] args) {buildMaxHeapify (srie); Heapsort (tri); imprimer (tri); } private static void buildMaxHeapify (int [] data) {// Seuls ceux sans enfants doivent créer le tas maximum, démarrer à partir du dernier nœud parent int startIndex = getParentIndex (data.length-1); }} / ** * Créer le tas maximum * * @ paramdata * @ paramheapsize nécessite la taille du tas maximum, qui est généralement utilisé en tri, car la valeur maximale est placée à la fin, la fin n'est plus classée comme le tas maximum * @ paramindex La position où le tas maximum est actuellement nécessaire * / Index STATIQUE MAXHEAPIFY (INT [] Data, INTRACKET {Index STATIC MAXHEAPif Point de courant avec les nœuds enfants gauche et droit int Left = GetChildLeftIndex (index); int droit = getChildRightIndex (index); Int plus grand = index; if (Left <heapSize && data [index] <data [gauche]) {plus grand = gauche; } if (reight <heapSize && data [le plus grand] <data [à droite]) {plus grand = droit; } // Après avoir obtenu la valeur maximale, il peut devoir être échangé. S'ils sont échangés, ses enfants peuvent ne pas être le plus grand tas. Il doit être réajusté si (plus grand! = Index) {int temp = data [index]; données [index] = données [plus importantes]; données [plus importantes] = temp; MaxHeapify (données, tasze, plus grande); }} / ** * Tri, la valeur maximale est placée à la fin. Bien que les données soient le plus grand tas, il devient incrémentiel après tri * * @ paramdata * / private static void heapsort (int [] data) {// échange avec l'en-tête à la fin, ajustez le tas maximum après échange pour (int i = data.length-1; i> 0; i -) {int temp = data [0]; data [0] = data [i]; data [i] = temp; MaxHeapify (données, i, 0); }} / ** * paramcurrent * @ return * / private static int getParentIndex (int current) {return (current-1) >> 1; } / ** * La position du nœud enfant actuel fait attention aux parenthèses, et la priorité d'addition est plus élevée * * @ paramcurrent * @ return * / private static int GetChildLeftIndex (int Current) {return (current << 1) +1; } / ** * Position du nœud enfant droit * * @ paramcurrent * @ return * / private static int GetChildRightIndEx (int courant) {return (current << 1) +2; } private static void print (int [] data) {int pre = -2; for (int i = 0; i <data.length; i ++) {if (pre <(int) getLog (i + 1)) {pre = (int) getLog (i + 1); System.out.println (); } System.out.print (data [i] + "|"); }} / ** * logo avec la base 2 * * @ paraparam * @ return * / private static double getLog (double param) {return math.log (param) /math.log (2); }}