binary heap cannot perform insert in O(1).
登录 | 论坛导航 -> 华新鲜事 -> 求学狮城 | 本帖共有 2 楼,分 1 页, 当前显示第 1 页 : 本帖树形列表 : 刷新 : 返回上一页
<<始页  [1]  末页>>
作者:Flying (等级:18 - 华新水车,发帖:16849) 发表:2003-11-14 15:20:28  楼主  关注此帖
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!!!
binary heap cannot perform insert in O(1).
Trace the insert algorithm for binary heap, and you'll know why.
Flying @way 吳穎暉
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版所有回复从这里展开收起列表
作者:Flying (等级:18 - 华新水车,发帖:16849) 发表:2003-11-14 17:20:06  2楼
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
sorry...I didn't notice the "best-case time" there
In that case, I re-read the question, and I think I'll post C as the answer.
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!原文 / 传统版 / WAP版所有回复从这里展开收起列表
论坛导航 -> 华新鲜事 -> 求学狮城 | 返回上一页 | 本主题共有 2 篇文章,分 1 页, 当前显示第 1 页 | 回到顶部
<<始页  [1]  末页>>

请登录后回复:帐号   密码