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

10

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 )log(n)2log(n)k=1n2log(k)

andrei
fonte

Respostas:

13

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 potencialwiiH

Φ(H)=iH2wi.

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 .dlog(n)2dO(1)O(logn)Φ(H)O(log(n)+Δ(Φ(H)))=O(logn)

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

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

A.Schulz
fonte
Tenho certeza de que você está correto, mas não entendi a inserção. Por que inalterado? Desculpe se a resposta é óbvia, mas você poderia expandir ? Eu não posso ver porque você teria um número negativo láΔ(Φ(H)))Δ
andrei
Δ(Φ(H)) refers to the potential difference - before and after the insert. It is in the insert case at most 2log(n). When you exchange two elements in the heap (bubble-up or bubble-down), then one weight gets +1, and the other gets -1 change, thus the potential (the sum of all weights) remains the same.
A.Schulz
How is repair O(1)? What is the use of the potential function in repairing the heap? Could you please clarify
Sohaib
@Sohaib: repair takes O(logn) time, but O(1) amortized time using the above potential function. There is no other use of the potential function than analyzing the amortized costs.
A.Schulz
@A.Schulz So this in essence means that given that the extract operation is done n number of times since each time the potential function would decrease by 2logn (may or may not increase equally upon repair). The overall complexity for such a thing would be constant time since eventually there would be no node in the tree. Am I right?
Sohaib