I'm trying to figure out how to do amortised analysis of heap insert and heap delete-min using potential function. We can assume, that insert is O(logn) and delete-min is O(logn) too.The goal is to prove, that amortised price of insert is O(logn) and amortised price of delete-min is O(1).Can't figure out how to create a potential function. POT.F = ?INSERT c = logn + (something from 0 to xlogn)DELETE-MIN c = logn + (something like -logn) Could you guys help me? I've figure out so far that difference between potentials should be from 0 to xlogn so INSERT price would be logn and for DELETE-MIN, difference should be somewhere abour -logn to get constant price.
Amortised analysis of binary heap insert and delete-min
algorithm analysis;data structures;runtime analysis;heaps;amortized analysis