从最大堆中获取最小元素的时间复杂度
在一次采访中有人问我：
从最大堆中获取最小元素的最佳时间复杂度是多少？
假定堆大小已知并且使用数组将堆实现为二进制堆，我将其答复为O（1）。按照我的假设，最小值为heap_array[heap_size]。
我的问题是这个答案是否正确。如果没有，正确答案是什么？
回答：
不，那是不正确的。您唯一的保证是， 。换句话说， 树中的 。
正确答案是O（n）。在每个步骤中，您都需要遍历左右两个子树，以搜索最小元素。实际上，这意味着您需要遍历所有元素以找到最小值。
以上是 从最大堆中获取最小元素的时间复杂度 的全部内容， 来源链接： utcz.com/qa/424821.html
