对于以下问题
问题3您将获得一个包含n个元素的堆，这些元素支持Insert和Extract-Min。您可以在O(logn(时间内完成以下哪项任务？
- 查找存储在堆中的元素的中值
- 查找存储在堆中的第五小元素
- 查找堆中存储的最大元素
- 找到存储在heap中的元素的中值
为什么是"查找堆中存储的最大元素"不正确，我在这里的理解是，你可以使用logN时间到达堆的底部，其中一个元素必须是最大的元素。
"查找存储在堆中的第五小元素"这应该需要持续的时间，对吧，因为你最多只需要下5层？
"找到存储在堆中的元素的中值"这需要O(n(时间吗？因为我们提取n个元素的最小值来获得排序数组，并取o(1(来找到它的中值？
这取决于insert和extract-min操作的运行时间。在传统堆中，两者都需要ϴ(logn(时间。然而，在基于手指树的堆中，只有插入需要ϴ(logn(时间，而提取min需要O(1(时间。在那里，你可以找到O(5(=O(1(时间中的第五小元素，以及O(n/2(=O。您还可以找到O(n(时间中最大的元素。
为什么是"查找堆中存储的最大元素"不正确，我在这里的理解是，你可以使用logN时间到达堆的底部，其中一个元素必须是最大的元素。
堆的最低级别包含一半的元素。更正确地说，堆中有一半的元素是叶子——没有子元素。堆中最大的元素就是其中之一。那么，要找到堆中最大的元素，就需要检查n/2个项。除了堆只支持insert和extract-min之外，因此您最终不得不对每个元素调用extract-min。找到最大的元素将花费O(n log n(时间。
"查找存储在堆中的第五小元素"这应该需要持续的时间，对吧，因为你最多只需要下5层？
这可以在log(n(时间内完成。实际上是5*log(n(，因为您必须调用extract min五次。但我们忽略了持续的因素。然而，它不是恒定的时间，因为extract min的复杂性取决于堆的大小。
"找到存储在堆中的元素的中值"这需要O(n(时间吗？因为我们提取n个元素的最小值来获得排序数组，并取o(1(来找到它的中值？
中值是中间元素。因此，您只需要从堆中删除n/2个元素。但是从堆中删除一个项是一个log(n(操作。所以复杂性是O(n/2 logn(，因为我们在算法分析中忽略了常数因子，所以它是O(n-logn(。