Función potencial extracto de montón binario max O (1)

Necesito ayuda para calcular la función potencial de un montón máximo para que el extracto máximo se complete en tiempo amortizado. Debo agregar que no entiendo bien el método potencial. $O(1)$

Sé que la función de inserción debería "pagar" más para reducir el costo de la extracción, y esto tiene que ver con la altura del montón (si da la altura del montón si inserte be o ) $\lfloor \log(n) \rfloor$ $2\log(n)$ $\sum_{k=1}^n 2\log(k)$

data-structures runtime-analysis heaps amortized-analysis andrei
fuente

Respuestas:

Intenta lo siguiente:

El peso de un elemento en el montón es su profundidad en el árbol binario correspondiente. Entonces el elemento en la raíz tiene un peso cero, sus dos hijos tienen un peso 1 y así sucesivamente. El lo define como función potencial $w_i$ $i$ $H$

Φ (H) = \sum_{i \in H} 2 w_{i} .

$\Phi(H)=\sum_{i\in H}2 w_i.$

$d$ $\log(n)$ $2d$ $O(1)$ $O(\log n)$ $\Phi(H)$ $O(\log(n)+\Delta(\Phi(H)))=O(\log n)$

$2\log(n)$ $O(1)$

Si tiene una pregunta general sobre la función potencial, debe plantearla como una pregunta diferente.

A.Schulz
fuente

Δ (Φ (H)))

$\Delta(\Phi(H)))$

Δ

$\Delta$

Δ (Φ (H))

$\Delta(\Phi(H))$

2 \log (n)

$2\log(n)$

¿Cómo es la reparación O (1)? ¿Para qué sirve la función potencial en la reparación del montón? ¿Podría

aclararme

O (\log n)

$O(\log n)$

O (1)

$O(1)$

@ A.Schulz Entonces, en esencia, esto significa que dado que la operación de extracción se realiza varias veces, ya que cada vez que la función potencial disminuiría en 2logn (puede aumentar o no de manera equitativa después de la reparación). La complejidad general para tal cosa sería un tiempo constante ya que eventualmente no habría ningún nodo en el árbol. Estoy en lo cierto?

Sohaib