在构建堆时，我们从树的中间开始调用max_heapify(A,i)，即floor(n/2)，直到以递减的方式调用根来维护堆属性。我已经读了一些背后的原因，但我仍然不明白为什么。请问有人可以解释原因吗？
谢谢你。
最佳答案
如果以这种方式进行操作，则在最坏的情况下时间复杂度是线性的(证明的想法是观察到，当一个元素向下过滤时，另一个元素会向上移动，并且一旦向上移动它就永远不会下降。因此，每片叶子下降的次数为零，每片叶子上方一层的最多上升的次数为1，依此类推，如果我们显式地计算该和，结果就是O(N))。
如果我们从头开始并向上筛选元素，则时间复杂度为O(N log N)(例如，如果数组是反向的)。
综上所述，这种方式更有效。
注意:我们本来可以从最后一个元素开始，但是叶子永远都不会下降，因此它将毫无用处(不过时间复杂度将保持线性)。
关于algorithm - 构建堆时从数组中间调用heapify的原因，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40822475/