1

I want to increase the value of all the leaf elements. All with index larger than *floor[n/2].

1) Call HEAP-INCREASE-KEY(A,i,key) for each leaf element

2) Increase the key of each leaf element to the new value, then call BUILD-MAX-HEAP(A)

Which way would be more efficient and why?

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). The running time of Heap-Increase-Key is O(lgn).

HEAP-INCREASE-KEY(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()

BUILD-MAX-HEAP(A)

A.heap-size = A.length
for i = *floor[A.length/2] downto 1
    MAX-HEAPIFY(A,i)

if you need to know what max-heapify is

MAX-HEAPIFY(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)
4

1 回答 1

1

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.

于 2013-10-10T01:44:11.893 回答