逐个获取元素时自上而下的堆构造

Question

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

Answer 1

构建堆方法(您称之为自上而下的构建(是O(n(。因此，每次插入堆都是一个O(n(运算。相比之下，在底部插入并向上筛选，在最坏的情况下是O(logn(，但在实践中更接近O(1(。请参阅堆插入的O(1(平均大小写复杂度的参数。

如果你真的必须在收到一个项目后立即插入到堆中，那么除了进行标准插入之外，你没有其他可行的选择：添加到堆的末尾并进行筛选。