Je réalise que c'est une vieille question, et peut-être cela devrait être une réponse à un commentaire de la accepté de répondre, mais hélas, je n'ai pas la condition de la réputation (sur ce site) pour poster un commentaire... :). Aussi, je peux fournir plus de détails ici.
La accepté de répondre donne la bonne analyse pour montrer que buildHeap s'exécute en O(n) fois. Mais la question a été posée:
"C'est une bonne explication...mais pourquoi est-il alors que le tas de tri s'exécute en O(n log n). Pourquoi ne pas le même raisonnement s'applique à des tas de tri?"
Une réponse a été donnée dans les commentaires qui suggère que la différence réside dans siftDown vs siftUp que je pense un peu à côté du point (ou est tout simplement trop brève pour qu'il soit clair). En effet, vous n'avez pas besoin d'utiliser siftUp lors de la mise en œuvre d'un tas binaire ou d'un segment de tri.
Rappelez-vous que le segment de la propriété spécifie que chaque nœud doit être plus petite que ses deux enfants. Le tamisage vers le bas et le tamisage sont essentiellement la même opération dans des directions opposées: déplacement d'un nœud fautif jusqu'à ce qu'il satisfait la propriété tas. Le tamisage se déplace vers le bas d'un nœud vers le bas jusqu'à ce qu'il est plus petit que ses enfants. Le tamisage se déplace d'un nœud jusqu'à ce qu'elle est supérieure à celle de son parent. Le nombre d'opérations nécessaires pour chaque opération est proportionnelle à la distance du nœud peut avoir à se déplacer. Pour siftDown, c'est la distance entre le bas de l'arbre, de sorte siftDown est cher pour les nœuds en haut de l'arbre. Avec siftUp, le travail est proportionnel à la distance à partir du haut de l'arbre, de sorte siftUp est cher pour les noeuds sur le bas de l'arbre.
Une façon de construire un segment à partir d'un tableau d'éléments non triés est de commencer au sommet de la pile et de l'appel siftUp sur chaque élément. À chaque étape, préalablement tamisée éléments de forme valide d'un tas, et le tamisage de l'élément suivant jusqu'le place dans une position valide dans le tas. Ainsi, après le tamisage de chaque nœud, tous les éléments de satisfaire la propriété tas. Cependant, la grande majorité des nœuds sont dans le bas de l'arbre (près de la moitié dans le fond de la couche seul) et en appelant siftUp est cher pour ces nœuds.
Une approche plus efficace est celui qui est indiqué par le a accepté réponse: commencez par le bas et appel siftDown. Maintenant, les nœuds dans la couche de fond ne bouge pas du tout (ils sont déjà plus petits que leurs inexistante enfants). Les nœuds dans l'avant-dernière couche déplacer sur une distance maximale de un. Le compromis est que les nœuds en haut peut-être déplacer beaucoup, mais il y a beaucoup moins de nœuds près du haut de l'arbre que le fond. Le travail effectué peut être délimitée comme suit: la moitié des nœuds sont dans la couche de fond et nécessitent 0 travail. Un quart sont dans la deuxième couche et 1 travail de chacun. Un huitième besoin de 2 travaux, etc. Si h = log n est la hauteur, la somme est
0* n/2 + 1 * n/4 + 2 * n/8 + ... + h * 1.
Bien que ce n'est pas une série (c'est juste une somme finie), vous pouvez utiliser la série de Taylor pour montrer qu'elle est bornée par une constante multiple de n. Si l'intérêt est là, je peux modifier ma réponse à inclure les détails.
Alors, pourquoi ne tas de tri nécessite O(n log n) le temps? Eh bien, segment tri se fait en deux étapes: buildHeap, ce qui nécessite O(n) fois si en œuvre de façon optimale, suivi en supprimant les éléments dans l'ordre:
while (!empty)
deleteMin
Clairement, la boucle s'exécute n fois (une fois pour chaque élément). La quantité de travail nécessaire à chaque itération? deleteMin travaille en remplaçant le plus petit élément (l'élément à la racine de l'arbre) avec le dernier élément dans l'arborescence, puis de l'appel d'siftDown jusqu'à ce que le segment de la propriété est satisfaite de nouveau. Notez que, contrairement à buildHeap, où pour la plupart des nœuds nous appelons siftDown à partir du bas de l'arbre, nous l'appelons maintenant siftDown à partir du haut de l'arbre à chaque itération! Bien que l'arbre est en décroissance, la distance, chaque nœud peut avoir à se déplacer lors de l'appel de siftDown est proportionnelle à la hauteur de l'arbre. La hauteur de l'arbre reste constante jusqu'à ce que vous avez retiré la première moitié des nœuds (lorsque vous effacer la partie inférieure de la couche complètement). Alors pour le prochain trimestre, la hauteur est h - 1. Alors maintenant, vous obtenez une somme de
h*n/2 + (h-1)*n/4 + ... + 0 * 1.
Avis de l'interrupteur: maintenant, le zéro cas de travail correspond à un seul nœud et le h de travail cas correspond à la moitié des nœuds. Nous avons passé le groupe, où la plupart du travail est fait. En bref, le meilleur lié, nous pouvons obtenir est que nous avons besoin de O(log n) pour chaque suppression (et c'est en fait la valeur correcte pour la majorité des nœuds). Chaque suppression nécessite O(log n) le temps, de sorte que la totalité de la boucle est O(n log n) en temps.
Donc, les deux étapes de tas de tri nécessite O(n) le temps de construire le tas et O(n log n) pour supprimer chaque nœud dans l'ordre, donc la complexité est O(n log n).
Remarque: Si vous voulez faire des tas de tri en place, vous êtes probablement mieux de construire un max de tas, puis en supprimant l'élément le plus important et le placer à la fin du segment de mémoire (depuis le tas diminue, ce spot n'est plus une partie de la masse, et peut être utilisé pour stocker les articles). Fondamentalement, il trie en plaçant le plus grand élément à la fin de la liste, puis répéter jusqu'à ce que le plus petit élément est atteint.
