CS Practice Book上的第60题

AutoseaUID: 192045

60. Consider the following possible data structures for a set of n distinct integers.
I. A min-heap
II. An array of length n sorted in increasing order
III. A balanced binary search tree
For which of these data structures is the number of steps needed to find and remove the 7th largest element O(logn) in the worst case?

(A) I only (B) II only (C) I and II (D) I and III (E) II and III

答案:E

为什么会有II？
在数组中找第7大的元素，可以用下标直接找到，删除只要移动6个元素就行了。总共是O(1)的复杂度

youarestupidUID: 2123815

I. 如果是max-heap应该也可以做到logn数量级查找第7大元素，对吧！？
II. 最好的是O(1)，如果采用二分查找最差也是O(logn)了吧
III. AVL查找最坏是O(logn)；删除要麻烦一点，需要重新调整后面6个节点的关系，不需要动前面n－7个节点的树形结构，因为只重构6个节点在树中的位置，代价最坏应该是O(1)

楼主帮忙解释一下III呗！？

感觉这个题挺别扭的

yuzisunUID: 155784

调用一次minheap是logn,找第七大的话个人感觉需要nlogn

yuren78UID: 2111432

If you check the definition of  Big O, you should know that. If it is asking tight bound, then it's a different story.

Just like 1 <2, of course, it is <3 too.

AutoseaUID: 192045

Originally posted by yuren78 at 2005-11-1 08:10
If you check the definition of  Big O, you should know that. If it is asking tight bound, then it's a different story.

Just like 1 <2, of course, it is <3 too.

有道理。发现ETS出的题对基本概念考得很细，做题时要小心啊

yuren78UID: 2111432

Autosea, thank you for your reply to my question on TestMagic.com.