Borne inférieure sur heapsort?

Question

Il est bien connu que le temps d'exécution pire cas pour heapsort est O (nlogn), mais je vais avoir du mal voyant pourquoi. En particulier, la première étape de tri par tas (faisant un tas max) prend du temps T (n). Il est ensuite suivi par des suppressions de tas de n. Je comprends pourquoi chaque suppression de tas prend du temps O (logn); le rééquilibrage de la pile implique une opération de bulles d'air vers le bas qui prend du temps O (h) de la hauteur du tas, et h = O (lg n). Cependant, ce que je ne vois pas pourquoi cette deuxième étape devrait prendre O (nlogn). Il semble que tout dequeue tas individuel ne serait pas nécessairement la cause du nœud déplacé vers le haut à bouillonner tout le long de l'arbre.

Ma question est - ce que quelqu'un sait d'une bonne preuve borne inférieure pour le comportement le plus de cas de heapsort

Answer 1

Je l'ai fait un peu de moi-même creuser et il semble que ce résultat est en fait assez récent! La première preuve borne inférieure je peux trouver est de 1992, bien que lui-même heapsort a été inventé en 1964.

La preuve borne inférieure formelle est due à « l'analyse des Heapsort » papier de Schaffer et Sedgewick. Voici une version légèrement paraphrasé de la preuve qui passe sous silence certains détails techniques.

Pour commencer, supposons que n = 2 ^k - 1 pour un certain k, ce qui garantit que nous avons un tas binaire complet. Je vais vous montrer comment gérer ce cas séparément plus tard. Parce que nous avons 2 ^k - 1 éléments, le premier passage de heapsort sera, en T (n), construire un tas de hauteur k. Maintenant, considérons la première moitié des dequeues de ce tas, qui élimine 2 ^k-1 nœuds du tas. La première observation clé est que si vous prenez le tas de départ et marquez tous les nœuds ici qui finissent effectivement se dequeued, ils forment un sous-arbre du tas (à savoir tous les noeuds qui obtiennent dequeued a un parent qui obtient également dequeued). Vous pouvez voir cela parce que si cela ne le cas, alors il y aurait un nœud dont le parent (plus) ne se dequeued que le nœud lui-même a été dequeued, ce qui signifie que les valeurs sont hors d'usage.

Maintenant, examiner comment les nœuds de cet arbre sont répartis sur le tas. Si vous étiquetez les niveaux du tas 0, 1, 2, ..., k - 1, alors il y aura un certain nombre de ces noeuds dans les niveaux 0, 1, 2, ..., k - 2 (qui est, tout sauf le niveau bas de l'arbre). Pour que ces noeuds pour obtenir dequeued du tas, alors ils doivent se permuté à la racine, et ils ne se permutés d'un niveau à la fois. Cela signifie que d'une façon à la limite inférieure de l'exécution heapsort serait de compter le nombre de swaps nécessaires pour que toutes ces valeurs jusqu'à la racine. En fait, c'est exactement ce que nous allons faire.

La première question que nous devons répondre est - combien le plus grand 2 ^k-1 nœuds ne sont pas dans le niveau bas du tas? On peut montrer que ce n'est pas supérieure à 2 ^k-2 par contradiction. Supposons qu'il y ait au moins 2 ^k-2 + 1 des plus grands noeuds dans le niveau bas de l'échelle. Ensuite, chacun des parents de ces nœuds doivent aussi être de grands noeuds de niveau k - 2. Même dans le meilleur des cas, cela signifie qu'il doit y avoir au moins 2 ^k-3 + 1 grands nœuds de niveau k - 2, qui alors des moyens qu'il y aurait au moins 2 ^k-4 + 1 grands nœuds de niveau k - 3, etc. en résumé sur tous ces nœuds, nous obtenons qu'il ya 2 ^k-2 + 2 ^k-3 + 2 ^k-4 + ... + 2 ⁰ + k grands noeuds. Mais cette valeur est strictement supérieure à 2 ^k-1 , contredisant le fait que nous travaillons avec seulement 2 ^k-1 nœuds ici.

D'accord ... nous savons maintenant qu'il ya au plus 2 ^k-2 grand noeuds dans la couche inférieure. Cela signifie que il doit y avoir au moins 2 ^k-2 de grands noeuds dans les premières couches k-2. Nous demandons maintenant - quelle est la somme, sur tous ces nœuds, de la distance de ce nœud à la racine? Eh bien, si nous avons 2 ^k-2 nœuds quelque part positionné dans un tas complet, puis au plus 2 ^k-3 d'entre eux peut être le premier k - 3 niveaux, et donc il y a au moins 2 ^k-2 - 2 ^k-3 = 2 ^k-3 noeuds lourds du niveau k - 2. Par conséquent , le nombre total d'échanges qui doivent être effectuées sont au moins (k - 2) 2 ^k-3 . Etant donné que n = 2 ^k -1, k = T (n lg), et ainsi cette valeur est T (n lg n) selon les besoins.

Answer 2

Réponse d'observation simple est la suivante: Les éléments en tas sont:

1
2
4
8
...
2^[log(n/4)]
and last level has between (1..2^[log(n/2)]) ==> (1,[n/2]) item, (by [] I mean Ceiling not roof)

par exemple si vous avez 7 élément:

1
2
4

et si vous avez 8 élément:

1
2
4
1

Il y a 2 autre arbre tas, tout d'abord au moins n / 4 - 1 éléments d'un tas sont en dernier niveau, ou non, donc il y a au moins un objet de n/4 - 1 au niveau avant dernier, dans le premier cas, il prend O((n/4 - 1) * log(n/2)) pour supprimer des éléments de dernière niveau de tas, et dans le second cas il faut O((n/4 - 1) * log(n/4)) de supprimer des éléments de pré dernier niveau. donc dans les deux cas, il prend O (n log (n)) juste pour n / 4 - 1 éléments, il est donc une borne (peut facilement dire qu'il est borne inférieure étanche) inférieure.

Answer 3

Voici une solution qui utilise CLRS termes:
Nous commençons par un tas max qui est un arbre binaire complet avec des éléments n.
On peut dire que, dans un binaire complet il y a des feuilles de n/2 et les nœuds internes de n/2.
itérations n/2 de HEAP-SORT supprimer les éléments les plus grands n/2 du tas.
Laissez S l'ensemble des éléments les plus grands n/2.
Il peut y avoir à la plupart des éléments de n/4 de S dans les feuilles car il doit y avoir n/4 plus d'entre eux dans les noeuds internes.
Laissez L être ces n/4 éléments les plus grands de S qui sont dans les feuilles.
Donc, s'il y a des éléments de n/4 de S au niveau 0 (le niveau de feuilles) il doit y avoir au moins n/8 d'entre eux au niveau 1.
Laissez P être ces éléments n/8 de S qui sont au niveau 1.
itérations n/2 de PGRPI-SORT peuvent donner les éléments de L un raccourci vers la racine puis sur le tas, mais les éléments de P doivent faire tout le chemin à la racine avant qu'ils ne soient retirés du tas.
Donc, il y a au moins des opérations de (n/8)(lgn-1), ce qui nous donne une durée de O (NLGN).
Maintenant, pour le cas d'un maximum tas qui ne dispose pas de toutes ses feuilles au niveau 0.
Que k soit le nombre de ses feuilles au niveau 0.
Après itérations k Entassé-SORT, on se retrouve avec un tas max qui est un arbre binaire complet avec lgn-1 hauteur.
Nous pouvons continuer notre preuve de la même façon.
Maintenant, pour le cas où il y a moins de feuilles de n/4 de S.
Que k soit le nombre d'éléments de S qui sont dans les feuilles au niveau 0.
Si k <= n/8 il doit y avoir au moins des éléments de n/8 de S au niveau 1.
En effet, il peut y avoir un total d'éléments de n/4 au dessus du niveau 1.
Nous continuons la preuve de la même façon.
Si k>n/8 il doit y avoir au moins des éléments de n/16 de S qui sont au niveau 1.
Nous continuons la preuve de la même façon.
Nous concluons que le temps d'exécution Entassé-SORT est O (NLGN).