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!!![最近不太好 (11-11 16:56, Long long ago)] [ 传统版 | sForum ][登录后回复]1楼

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[cigar (11-11 20:57, Long long ago)] [ 传统版 | sForum ][登录后回复]2楼

(引用 cigar: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 ca...)Correction: for max heap, delete mim should beO(logN) if we don't care the search time instead of O(1)[cigar (11-11 21:04, Long long ago)] [ 传统版 | sForum ][登录后回复]3楼

binary heap cannot perform insert in O(1).Trace the insert algorithm for binary heap, and you'll know why.[Flying (11-14 15:20, Long long ago)] [ 传统版 | sForum ][登录后回复]4楼

(引用 Flying:binary heap cannot perform insert in O(1).Trace the insert algorithm for binary heap, and you'll know why.)But I think it can-->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[cigar (11-14 16:24, Long long ago)] [ 传统版 | sForum ][登录后回复]5楼

(引用 cigar:But I think it can-->For example, for an array based min heap, inserting a value larger than the maximum of original heap will...)sorry...I didn't notice the "best-case time" thereIn that case, I re-read the question, and I think I'll post C as the answer.[Flying (11-14 17:20, Long long ago)] [ 传统版 | sForum ][登录后回复]6楼