Função potencial extrato de pilha binária max O (1)

Preciso de ajuda para calcular a função potencial de um heap máximo, para que o extrair max seja concluído em tempo amortizado. Devo acrescentar que não tenho uma boa compreensão do método potencial.$O(1)$

Eu sei que a função de inserção deve "pagar" mais para reduzir o custo da extração, e isso deve ser em relação à altura da pilha (se fornece a altura do heap deve a inserção ser ou )$\lfloor \log(n) \rfloor$$2\log(n)$$\sum_{k=1}^n 2\log(k)$

Tente o seguinte:

O peso de um elemento na pilha é sua profundidade na árvore binária correspondente. Portanto, o elemento na raiz tem peso zero, seus dois filhos têm peso 1 e assim por diante. Você define como função potencial$w_i$$i$$H$

Vamos agora analisar as operações de heap. Para inserir, adicione um novo elemento e adicione profundidade no máximo . Isso aumenta o potencial em e pode ser feito no tempo . Em seguida, você "borbulha" o novo elemento de heap para garantir a propriedade de heap. Isso leva tempo e deixa inalterado. Assim, os custos de inserção são .$d$$\log(n)$$2d$$O(1)$$O(\log n)$$\Phi(H)$$O(\log(n)+\Delta(\Phi(H)))=O(\log n)$

Agora considere o extractMin . Você remove a raiz e a substitui pelo último elemento na pilha. Isso diminui o potencial em , portanto, você pode se dar ao luxo de reparar a propriedade heap e, portanto, os custos amortizados agora são .$2\log(n)$$O(1)$

Se você tiver uma pergunta geral para a função em potencial, coloque isso como uma pergunta diferente.