Compte tenu d'un tableau de numéro, existe-t-il un algorithme O (n) pour construire un tas Max-Heap?
4 Réponses :
Je ne pense pas. Je pense que le mieux que vous puissiez faire est O (log n) ou un peu mieux avec quelque chose comme un tas de fib.
o (journal n) est o (n) (ie, si f est o (journal n) f si o (n) ).
Je pense qu'il devait avoir signifié O (n log n)?
Ce n'est pas clair pour moi. Je pense que les insertions dans un tas de fibonacci sont amortis O (1) et donc le bâtiment est amorti o (n) .
Construire des tas binaires Bottom-up est O (n) .
Si vous utilisez un Fibonacci Heap Vous obtenez Amortizetisé O (1) insertion. Vous pouvez donc construire un tas maximum en amortis O (n) d'un tableau.
La mise en œuvre de tels, je laisse comme un exercice *.
* Cependant, il existe des exemples de mise en œuvre liés sur la page Wikipedia.
Oui, il y a: Construire un tas .
+1. Plus pour le ton de la réponse que la réponse elle-même :)
Votre propre lien suggère que ce n'est pas possible. Cela aurait dû dire non il n'y a pas ...
@Peter: Devis du lien: "Par conséquent, le coût du recouvrement de tous les sous-arbres est le suivant: [équations SNIP] O (n)"
Oui, comme dans ce code: ( Pour obtenir pourquoi ceci est O (n) Regardez l'arborescence binaire complet: p> 1/8 éléments (dernier niveau, i> n / 8) sont enfoncés au plus 2 étapes -> N / 8 * 2 Opérations
... p>
push_heap code> est une fonction qui accepte un pointeur sur un tas et la taille du tas et pousse le haut de la taille de la tas jusqu'à ce que les conditions de tas soient respectées ou que le nœud atteigne le fond du tas). P>
N/4 * 1 + N/8 * 2 + N/16 * 3 + ... =
N/4 * 1 + N/8 * 1 + N/16 * 1 + ... +
N/8 * 1 + N/16 * 2 + ... =
N/4 * 1 + N/8 * 1 + N/16 * 1 + ... + // < N/2
N/8 * 1 + N/16 * 1 + ... + // < N/4
N/16 * 1 + ... + // < N/8
... = // N/2 + N/4 + N/8 + ... < N
Homme, vous avez rendu les maths beaucoup plus simples que l'article Wiki! Merci beaucoup!
Quoi pour cette entrée: 1, 2, 3, 4, 5, 6, 7, 8, 9. Je pense que cela devrait être O (nlogn)?
Peut-être que si votre entrée est déjà commandée correctement.
@Frustration ...: Ce n'est pas commandé.