À l'école, nous apprenons actuellement les algorithmes de tri en Java et j'ai obtenu pour mes devoirs le tri en tas. J'ai fait ma lecture, j'ai essayé de trouver autant que je pouvais, mais il me semble que je ne peux tout simplement pas comprendre le concept.
Je ne vous demande pas de m'écrire un programme Java, si vous pouviez simplement m'expliquer le plus simplement possible le fonctionnement du tri de tas.
Bon, donc en gros, vous prenez un tas et tirez le premier nœud dans le tas comme le premier nœud est garanti d'être le plus grand / plus petit selon le sens du tri. La chose la plus délicate est de ré-équilibrage / création du tas dans la première place.
Deux étapes ont été nécessaires pour moi de comprendre le tas de processus - tout d'abord penser à cela comme un arbre, obtenir ma tête autour de lui, puis en tournant l'arbre dans un tableau de sorte qu'il pourrait être utile.
La deuxième partie est essentiellement parcourir l'arbre en largeur d'abord, de gauche à droite à l'ajout de chaque élément dans le tableau. Si l'arbre suivant:
73
7 12
2 4 9 10
1
Serait {73,7,12,2,4,9,10,1}
La première partie se fait en deux étapes:
Donc, pour heapify une liste de numéros que vous ajoutez à chacun de le tas, puis à la suite de ces deux étapes dans l'ordre.
Pour créer mon tas ci-dessus, je vais ajouter 10 pour la première c'est le seul nœud de façon à ne rien faire. Ajouter 12 comme il est enfant sur la gauche:
10
12
Cela satisfait 1, mais pas les 2, donc je vais les échanger autour de:
12
10
Ajouter 7 - rien à faire
12
10 7
Ajouter 73
12
10 7
73
10 < 73 ainsi le besoin de swap ceux:
12
73 7
10
12 < 73 ainsi le besoin de swap ceux:
73
12 7
10
Ajouter 2 - rien à faire
73
12 7
10 2
Ajouter 4 - rien à faire
73
12 7
10 2 4
Ajouter 9
73
12 7
10 2 4 9
7 < 9 - swap
73
12 9
10 2 4 7
Ajouter 1 - rien à faire
73
12 9
10 2 4 7
1
Nous avons notre tas :D
Maintenant, vous venez de supprimer chaque élément à partir du haut, la permutation dans le dernier élément au sommet de l'arbre, à chaque fois, puis de le ré-équilibrage de l'arbre:
Prenez 73 rebutant 1 à sa place
1
12 9
10 2 4 7
1 < 12 - donc on les échange
12
1 9
10 2 4 7
1 < 10 - afin de les échanger
12
10 9
1 2 4 7
Prendre 12 hors - remplacer par 7
7
10 9
1 2 4
7 < 10 - swap
10
7 9
1 2 4
Prendre 10 hors - remplacer par 4
4
7 9
1 2
4 < 7 - swap
7
4 9
1 2
7 < 9 - swap
9
4 7
1 2
Prendre 9 - remplacer les 2
2
4 7
1
2 < 4 - swap
4
2 7
1
4 < 7 - swap
7
2 4
1
Prendre 7 hors remplacer par 1
1
2 4
1 < 4 - swap
4
2 1
4 - remplacer par 1
1
2
1 < 2 - l'échange de
2
1
Prendre 2 - remplacer par 1
1
Prendre 1
Liste triée alto.
Une façon de penser à des tas de tri est comme un habilement version optimisée de tri de la sélection. Dans la sélection de tri, le tri fonctionne par à plusieurs reprises de trouver le plus grand élément non encore placé correctement, puis le mettre dans le prochain bon endroit dans le tableau. Cependant, la sélection de tri s'exécute en temps O(n2), parce qu'il y a à faire, n tours de trouver le plus grand élément d'un ensemble (et il peut y avoir jusqu'à n éléments différents à regarder) et de la mettre en place.
Intuitivement, segment tri fonctionne par la construction d'une structure de données appelée un tas binaire, ce qui permet d'accélérer jusqu'à trouver le plus grand élément de la non placées les éléments du tableau. Binaire tas de soutenir les opérations suivantes:
À un niveau très élevé, l'algorithme fonctionne comme suit:
Il trie le tableau car les éléments retournés par Supprimer-Max sont dans l'ordre décroissant. Une fois que tous les éléments ont été supprimés, le tableau est ensuite trié.
Tas de tri est efficace, car l' Insérer et Supprimer-Max opérations sur un segment à la fois exécuter en O(log n) le temps, ce qui signifie que n les insertions et les suppressions qui peut être fait sur le tas en O(n log n) en temps. Une analyse plus précise peut être utilisé pour montrer que, en fait, il faut Θ(n log n), quel que soit le tableau d'entrée.
Généralement, les tas de tri utilise deux principales optimisations. Tout d'abord, le tas est généralement construit en place à l'intérieur de la matrice par le traitement de la matrice elle-même comme une représentation compressée du tas. Si vous regardez un heapsort mise en œuvre, vous verrez habituellement des utilisations inhabituelles de la matrice des indices reposant sur la multiplication et la division par deux; ces accès de travail, car ils sont le traitement de la matrice comme un condensé de la structure de données. En conséquence, l'algorithme ne nécessite que O(1) auxiliaire de l'espace de stockage.
Deuxièmement, plutôt que de construire le tas un élément à la fois, le tas est généralement construit à l'aide d'un algorithme spécialisé qui s'exécute en temps Θ(n) pour construire le tas en place. Il est intéressant de noter, dans certains cas, cela finit par rendre le code plus facile à lire parce que le code peut être réutilisé, mais l'algorithme lui-même devient un peu plus compliqué à comprendre et à analyser.
Vous verrez souvent heapsort fait avec un ternaire tas. Cela a l'avantage d'être légèrement plus rapide en moyenne, mais si vous trouvez un heapsort de mise en œuvre de l'aide sans savoir ce que vous cherchez, il peut être assez difficile à lire. D'autres algorithmes utilisent également la même structure générale, mais de plus en plus complexe tas de structure. Smoothsort utilise beaucoup plus compliqué que tas pour obtenir O(n) dans le meilleur des cas de comportement tout en conservant O(1) utilisation de l'espace et de O(n log n) le pire des cas, le comportement. Peuplier de tri est similaire à smoothsort, mais avec O(log n) l'utilisation de l'espace et des performances légèrement meilleures. On peut même penser classique algorithmes de tri comme le tri par insertion et tri de sélection que des tas de trier les variantes.
Une fois que vous avez une meilleure compréhension de heapsort, vous voudrez peut-être chercher dans le introsort algorithme qui combine quicksort, heapsort, et le tri par insertion pour produire un très algorithme de tri rapide qui combine la force de quicksort (tri rapide en moyenne), heapsort (excellent pire des cas, le comportement), et l'insertion de tri (tri rapide pour les petits tableaux). Introsort est ce qui est utilisé dans de nombreuses implémentations de C++ std::sort de la fonction, et n'est pas très difficile à mettre en œuvre vous-même une fois que vous avez un travail heapsort.
Espérons que cette aide!
Je vais voir comment je vais répondre à cela, parce que mon explication pour des tas de tri et de ce qu'est un tas est un peu...
...euh, terrible.
De toute façon, tout d'abord, nous ferions mieux de vérifier ce qu'est un Segment de mémoire est:
Comme pris de Wikipédia, un segment de mémoire est:
En informatique, un segment de mémoire est une institution spécialisée des arbres, la structure de données qui satisfait la propriété tas: si B est un nœud enfant de l'Un, puis sur la touche(A) ≥ touche(B). Cela implique qu'un élément avec la plus grande clé est toujours dans le nœud racine, et donc, un tel segment est parfois appelé un max-heap. (Sinon, si la comparaison est inversée, le plus petit élément est toujours dans le nœud racine, ce qui résulte en une min-tas.)
Assez souvent, un tas est un arbre binaire tel que tous les enfants d'un nœud sont plus petits que ce nœud.
Maintenant, segment tri est un O(n lg n)) algorithme de tri. Vous pouvez lire un peu sur le sujet ici et ici. Il réussit plutôt bien par mettre tous les éléments de ce que vous êtes en essayant de trier en un tas, puis la construction du tableau trié à partir de l'élément le plus large à la plus petite. Vous allez garder sur la restructuration de la tas, et depuis le plus grand élément est à la racine du tas en tout temps, vous pouvez simplement continuer à prendre cet élément et de le mettre à l'arrière du tableau trié. (Qui est, vous allez construire le tableau trié dans le sens inverse)
Pourquoi cet algorithme en O(n lg n))? Parce que toutes les opérations sur un tas de O(lg(n)) et comme un résultat, vous ferez n opérations, résultant en un temps de fonctionnement total de O(n lg n)).
J'espère que mon terrible coup de gueule vous a aidé! C'est un peu verbeux; désolé...
Je me souviens de mon Algorithme d'analyse de professeur pour nous dire que le tas algorithme de tri fonctionne comme un tas de gravier:
Imaginez que vous avez un sac rempli de gravier, et de vous vider sur le sol: les Grandes pierres seront probablement rouler vers le bas et de petites pierres (ou de sable) restera sur le dessus.
Vous prenez maintenant le très haut du tas et l'enregistrer à la plus petite valeur de votre tas. Mettre de nouveau le reste de votre tas dans votre sac, et répétez. (Ou vous pouvez l'obtenir à l'opposé de l'approche et obtenir la plus grosse pierre que vous avez vu rouler sur le sol, l'exemple est toujours valable)
C'est plus ou moins la manière la plus simple que je connais pour expliquer comment tas de tri fonctionne.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
