time-complexity - 逐个获取元素时自上而下的堆构建

Question

所以我读到，当你一个一个地获取元素时，你应该使用自下而上的堆构造而不是自上而下的 heapify，但是如果我每次添加新元素时都使用 heapify 算法，基本上从 n/ 开始做同样的事情每次我在数组中添加一个元素时，2 对 1 heapify(i) 的事情，这种方法在使用 bittom up heap 构造方面有什么缺点，时间复杂度是多少

Answer 1

'build-heap' 方法（你称之为自上而下的构建）是 O(n)。所以每次插入堆都是一个 O(n) 操作。与在底部插入并向上筛选相比，在最坏的情况下为 O(log n)，但在实践中更接近 O(1)。请参阅堆插入的 O(1) 平均情况复杂度的参数。

如果您确实必须在收到项目后立即插入到堆中，那么除了进行标准插入之外，您实际上没有可行的选择：添加到堆的末尾并筛选。