The second one is more efficient.
1) Call HEAP-INCREASE-KEY(A,i,key) for each leaf element
The number of leaf elements is O(n)
. The time for HEAP-INCREASE-KEY(A,i,key)
is O(lgn)
. So the time complexity for the first solution is O(nlgn)
.
2) Increase the key of each leaf element to the new value, then call BUILD-MAX-HEAP(A)
To build a heap from scratch only takes linear time. So the time complexity for the second solution is O(n)
.
A little extra information, Each call to Max-Heapify costs O(lgn) time, and Build-max-heap makes O(n) such calls. Thus, the running time is O(nlgn).
If this statement was provided in your homework, then the time complexities for both solutions are the same. However, you are able to build a max heap in linear time rather than O(nlgn)
time.