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

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 ) )$\lfloor \log(n) \rfloor$$2\log(n)$$\sum_{k=1}^n 2\log(k)$

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 potentielle$w_i$$i$$H$

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 ) + Δ ( Φ $d$$\log(n)$$2d$$O(1)$$O(\log n)$$\Phi(H)$ .$O(\log(n)+\Delta(\Phi(H)))=O(\log n)$

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 ) .$2\log(n)$$O(1)$

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