我想增加所有叶元素的值。指数均大于*楼层[N/2]。
1）为每个叶元素调用HEAP-INCREASE-KEY（A，i，KEY）
2）将每个叶元素的键增加到新值，然后调用BUILD-MAX-HEAP（A）
哪种方式更有效？为什么？
一点额外的信息，每次调用max heapify会花费o（lgn）时间，而build max heap会发出o（n）这样的调用。因此，运行时间为o（nlgn）。堆递增键的运行时间为o（lgn）。
堆增加键（a，i，key）
if key<A[i]
error "new key is smaller than current key.
A[i]
while i>1 and A[Parent(i)]<A[i]
exchange A[i] with A[Parent(i)]
i=Parent()
构建最大堆（A）
A.heap-size = A.length
for i = *floor[A.length/2] downto 1
MAX-HEAPIFY(A,i)
如果你想知道麦克斯·希帕菲是什么
麦克斯-赫帕菲（A，i）
l=Left(i)
r=Right(i)
if l<=A.heap-size and A[l] > A[i]
largest = l
else largest = i
if r<=A.heap-size and A[r] > A[largest]
largest = r
if largest not equal i
exchange A[i] with A[largest]
MAX-HEAPIFY (A.largest)
最佳答案
第二个更有效。
1）为每个叶元素调用HEAP-INCREASE-KEY（A，i，KEY）
叶元素的数量是O(n)。HEAP-INCREASE-KEY(A,i,key)的时间是O(lgn)。因此，第一解的时间复杂度为O(nlgn)。
2）将每个叶元素的键增加到新值，然后调用
构建最大堆（A）
从头开始构建堆只需要线性时间因此，第二个解的时间复杂度为O(n)。
一点额外的信息，每次呼叫max heapify都要花费o（lgn）
时间，和build max heap进行o（n）这样的调用。因此，运行时间
是o（nlgn）。
如果这个陈述是在你的作业中提供的，那么两个解决方案的时间复杂度是相同的。但是，您可以在linear time而不是O(nlgn)时间内构建最大堆。