a question about running time: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!!!
My thoughts-->
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
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