提高所有葉子元素的價值的兩種解決方案

Question

我想增加所有葉子元素的價值。所有索引大於* floor [n/2]。

1）呼叫HEAP-INCREASE-KEY（A，I，密鑰）對每個葉元件

2）增加每個葉元件的新的值的鍵，然後調用BUILD-MAX-HEAP（A ）

哪種方式更有效率，爲什麼？

有一點額外的信息，每次調用Max-Heapify需要花費O（lgn）時間，而Build-max-heap則會讓O（n）這樣的調用。因此，運行時間是O（nlgn）。 Heap-Increase-Key的運行時間是O（lgn）。

HEAP增-KEY（A，I，鍵）

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) 

，如果你需要知道什麼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) 

Answer 1

秒一個更有效率。

1）呼叫HEAP-INCREASE-KEY（A，I，密鑰）對每個葉元件

簧片元件的數量是O(n)。 HEAP-INCREASE-KEY(A,i,key)的時間是O(lgn)。所以第一個解決方案的時間複雜度是O(nlgn)。

2）增加每個葉元素的鍵爲新的值，則調用 BUILD-MAX-HEAP（A）

要構建一個堆從頭只需要線性時間。所以第二種解決方案的時間複雜度爲O(n)。

一些額外的信息，馬克斯 - Heapify每次通話費用O（LGN） 時間，並內置最大堆使得O（n）的這樣的電話。因此，運行時間 是O（nlgn）。

如果在您的家庭作業中提供了此聲明，那麼這兩種解決方案的時間複雜性都是相同的。但是，您可以在linear time而不是O(nlgn)時間內構建最大堆。