My thoughts-->
登录 | 论坛导航 -> 华新鲜事 -> 求学狮城 | 本帖共有 3 楼,分 1 页, 当前显示第 1 页 : 本帖树形列表 : 刷新 : 返回上一页
<<始页  [1]  末页>>
作者:cigar (等级:2 - 初出茅庐,发帖:296) 发表:2003-11-11 20:57:49  楼主  关注此帖
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
Put your OWN COOL signature here!
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版所有回复从这里展开收起列表
作者:cigar (等级:2 - 初出茅庐,发帖:296) 发表:2003-11-11 21:04:56  2楼
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
Correction: for max heap, delete mim should be
O(logN) if we don't care the search time instead of O(1)
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版所有回复从这里展开收起列表
作者:cigar (等级:2 - 初出茅庐,发帖:296) 发表:2003-11-14 16:24:01  3楼
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
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版所有回复从这里展开收起列表
论坛导航 -> 华新鲜事 -> 求学狮城 | 返回上一页 | 本主题共有 3 篇文章,分 1 页, 当前显示第 1 页 | 回到顶部
<<始页  [1]  末页>>

请登录后回复:帐号   密码