heap - 最小堆的平均时间成本是多少

Question

查看我对数据结构的测试时，我注意到了一些东西，有人可以帮忙回答一下，在最小堆（优先级队列）中搜索最大键的平均时间成本（大 O）是多少，会是O(log N) 还是 O(N)？

Answer 1

在最小堆中搜索最大元素是O(N).

您必须到树中的最低级别（最多有一半的孩子）并检查它们中的每一个，因为它们彼此之间没有特定的顺序。

这将需要检查N/2哪些节点（假设您使用标准算法来查找最大值）是O(N).

如果您有兴趣在堆中查找最大元素，则可以使用最大堆。如果内存不是一个大问题，您可以同时使用最大堆和最小堆，这将允许您O(1)同时获得最大和最小元素。