Extrait de tas binaire de fonction potentielle max O (1)

10

J'ai besoin d'aide pour comprendre la fonction potentielle d'un tas max afin que l'extraction max soit terminée en temps amorti. Je dois ajouter que je n'ai pas une bonne compréhension de la méthode potentielle.O(1)

Je sais que la fonction d'insertion devrait "payer" davantage afin de réduire le coût de l'extraction, et cela doit être en ce qui concerne la hauteur du tas (si donne la hauteur du tas si le insérer soit 2 log ( n ) ou n k = 1 2 log ( k ) )Journal(n)2Journal(n)k=1n2Journal(k)

andrei
la source

Réponses:

13

Essayez ce qui suit:

Le poids d'un élément i dans le tas H est sa profondeur dans l'arbre binaire correspondant. Ainsi, l'élément dans la racine a un poids nul, ses deux enfants ont un poids 1 et ainsi de suite. Vous définissez comme fonction potentiellewjejeH

Φ(H)=jeH2wje.

Analysons maintenant les opérations de tas. Pour insérer, vous ajoutez un nouvel élément, ajoutez la profondeur au plus log ( n ) . Cela augmente le potentiel de 2 jours et peut être fait en temps O ( 1 ) . Ensuite, vous "bouillonnez" le nouvel élément de tas pour assurer la propriété de tas. Cela prend du temps O ( log n ) et laisse Φ ( H ) inchangé. Ainsi, les coûts d'insertion sont O ( log ( n ) + Δ ( Φ (Journal(n)2O(1)O(logn)Φ(H) .O(log(n)+Δ(Φ(H)))=O(logn)

Considérons maintenant l' extractMin . Vous retirez la racine et la remplacez par le dernier élément du tas. Cela diminue le potentiel de , vous pouvez donc vous permettre de réparer la propriété du tas, et donc les coûts amortis sont maintenant O ( 1 ) .2log(n)O(1)

Si vous avez une question générale sur la fonction potentielle, vous devez la poser comme une question différente.

A.Schulz
la source
Je suis sûr que vous avez raison mais je n'ai pas compris l'insertion. Pourquoi inchangé? Désolé si la réponse est évidente, mais pourriez-vous développer Δ ? Je ne vois pas pourquoi vous auriez un nombre négatif làΔ(Φ(H)))Δ
andrei
fait référence à la différence de potentiel - avant et après l'insert. Il est dans le cas d'insertion au plus 2 log ( n ) . Lorsque vous échangez deux éléments dans le tas (bulle vers le haut ou vers le bas), un poids obtient +1 et l'autre change -1, ainsi le potentiel (la somme de tous les poids) reste le même. Δ(Φ(H))2Journal(n)
A.Schulz
Comment est la réparation O (1)? Quelle est l'utilité de la fonction potentielle pour réparer le tas? Pourriez-vous clarifier
Sohaib
O(Journaln)O(1)
@ A.Schulz Donc, cela signifie essentiellement que, étant donné que l'opération d'extraction est effectuée n nombre de fois puisque chaque fois la fonction potentielle diminuerait de 2logn (peut ou non augmenter également lors de la réparation). La complexité globale d'une telle chose serait un temps constant car il n'y aurait finalement pas de nœud dans l'arbre. Ai-je raison?
Sohaib