我试着看http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-4-heaps-and-heap-sort/来理解堆和堆,但没有发现这一点。
我不明白麦克斯·希帕菲的作用。它看起来像一个递归函数,但不知怎么的,据说它在对数时间内运行,因为树的高度。
对我来说这毫无意义。在最坏的情况下,它不必反转每个节点吗?我不明白如果不反复接触每个节点,怎么能做到这一点。

最佳答案

以下是Max-Heapify的工作:
给定索引i处的节点,其左子树和右子树为最大堆,max-HEAPIFY将i处的节点向下移动到最大堆,直到它不再违反最大堆属性(即,节点不小于其子节点)。
节点在正确位置之前可以走的最长路径等于节点的起始高度每当节点需要在树中再下一层时,算法将只选择一个分支,而不会回溯。如果被heapified的节点是最大堆的根,那么它可以采用的最长路径是树的高度,或者O(log n)
max-heapify只移动一个节点。如果要将数组转换为最大堆,则必须确保所有子树都是最大堆,然后再转到根。为此,可以在n/2节点上调用MAX-HEAPIFY(leaves始终满足MAX heap属性)。
从CLR:

for i = floor(length(A)/2) downto 1
   do MAX-HEAPIFY(A,i)

因为您调用max-heapifyO(n)次,所以构建整个堆就是O(n log n)

08-06 12:04