Which of the following is not true about binary heap?
A. It supports insert() in O(LogN) worst-case time;
B. It supports insert() in O(1) best-case time;
C. It supports findMin() in O(logN) average time;
D. It supports deleteMin() in O(logN) worst-case time;
I think A and B should be right. But not sure about C and D.
Thanks a lot!!!

If it's a min heap: then we can find minimum in O(1) and delete minimum in O(logN);
if it's a max heap: then we can find minimum in O(N)(check all leaves) and delete minimum in O(N) ( taking search minimum first into account) or O(1) if we don't care the searching time

Pls correct me if i am wrong

O(logN) if we don't care the search time instead of O(1)

Trace the insert algorithm for binary heap, and you'll know why.

For example, for an array based min heap, inserting a value larger than the maximum of original heap will tabke O(1) time if bottom-up algorithm is applyied


Correct me if i am wrong

In that case, I re-read the question, and I think I'll post C as the answer.