heapifyUp（）メソッドの時間の複雑さはどのくらいですか？

Question

heapifyUp（）と heapifyDown（）メソッドを使用するヒープの実装をいくつか見てきました。私は上記のコードの時間複雑度は（Cormenに従って）O（N）である信じ

for(int i = heap_size/2; i >= 0; i--) 
    heapifyDown(i); 

：のように、我々はheapifyDown（）を使用して）（heapifyUpを実装することができませんでした。次のように

は今heapifyUp（）実装されました：私は間違っていないよ場合はO（LOGN）が優れているので、

while(i!=0 && arr[parent(i)]>arr[i]) 
{ 
     swap(arr[i],arr[parent(i)]); 
     i = parent(i); 
} 

は今、上記の実施のtimeplexityは今O（LOGN）

ですO（n）よりheapifyUp（）メソッドは確かに良くなりました。では、なぜCormenはヒープを構築するためにボトムアップheapify（方法1）を使用しますか？

私が間違っていて、どの実装が優れているか教えてください。

Answer 1

まず、2つのコードスニペットは全く異なる2つのことを行っています。 heapifyDown()のコードは、配列全体をヒープに再配置しています。それは配列の要素の半分を動かしており、時間の複雑さはプロセス全体のO（n）だけです。

投稿したheapifyUp()コードは、1つの要素をヒープの上に移動しています。時間の複雑さはO（log n）です。配列からヒープを構築するためにそのメソッドを使用する場合、合計時間の複雑さはO（n log n）になります。

heapifyUp()およびheapifyDown()は、2つの異なるものに使用され、それぞれの用途に理由があります。

heapifyUp()ヒープに項目を挿入するときに呼び出されます。アイテムを挿入するとき、アイテムはヒープの最後に配置され、ヒープを介してフィルタリングされます。最悪の場合はO（log n）です。平均的なケースは大きく異なります。平均で、項目の最下位行に属しているため、項目を移動する必要はありません。 1つのレベルを上に移動するだけで1/4の時間を費やすことができます。 2分の1レベルの移動が必要になる時間の1/8時間です。

heapifyDown()最小要素を削除するときに使用されます。最後の項目をヒープからルートに移動し、ヒープを通って適切な場所に移動します。上から下に移動するとき、heapifyDown（）はO（log n）の最悪の場合があります。平均の場合もまた、O（log n）である。

あなたが投稿したループは、heapifyDown()の第二、特別、使用することである：

for(int i = heap_size/2; i >= 0; i--) 
    heapifyDown(i); 

それは、ヒープ構造の利点を取っているので、これはO（n）があります。

まず、アイテムの半分しか動かないことに注意してください。第二に、すべてのアイテムが一番上から移動しているわけではありません。たとえば、ヒープが127のアイテム（ヒープが7レベルのフルヒープ）の場合、アイテムの64個は、すでにボトムレベルにあるため、検査されません。 32個のアイテムが1つの場所だけ移動します。ループを使用してヒープを作成する場合

64*0 + 32*1 + 16*2 + 8*3 + 4*4 + 2*5 + 1*6 
0 + 32 + 32 + 24 + 16 + 10 + 6 = 120 swaps 

120のスワップの最大：商品16は最大2つのレベル、等を移動あなたがで終わります。ヒープに新しい項目を挿入するとき

あなたははheapifyDown()を使用することができますが、平均的に挿入されたすべての項目は、それが下から挿入された場合よりもさらに移動する必要があるため、それは、heapifyUp()を使用するよりも遅くなります。