Amortized analysis on Heap

问题:

When I ran to this topic.

I read in this book on the bottom of page 5-1 that Binomial Queues, Fibonacci Heap and Skew Heap have O(1) amortized cost for insert operations and O(log n) amortized cost of delete operations. Next the authors write that the Pairing Heap has O(1) amortized cost for insert operations and O(log n) amortized cost for delete operations.

on this homework the third (3) assignment and solution on this link without defining the type of heap wrote O(log n) for insert and O(1) to delete.

on this homework another the author says a Binomial Heap has O(log n) for insert operations and O(1) amortized cost for delete operations.

The question is, which one is correct? I'm quite confused.

回答1:

Since the heap has a nonnegative number of elements, it's always the case that #inserts ≥ #deletes if we start with an empty heap. With amortized time bounds, O(1) insert/O(log n) delete hence implies O(log n) insert/O(1) delete, by changing the accounting so that an insert prepays its corresponding delete (if extant). There's no contradiction there.