sorting - ヒープソート時間の複雑さの深い理解

Question

大学でデータ構造コースを勉強したとき、次の公理を学びました。

ヒープへの新しい数値の挿入には、最悪の場合O(logn)かかります (リーフとして挿入されたときにツリー内のどのくらいの高さに到達するかによって異なります)。
空のヒープから開始して n 個の挿入を使用してnノードのヒープを構築すると、償却分析を使用してO(n)時間に合計されます
最小値の削除には、最悪の場合O(logn)時間がかかります (最後のリーフと交換された後、新しい最上位ノードがどれだけ低くなるかによって異なります)。
ヒープが空になるまで、すべての最小値を 1 つずつ削除するには、O(nlogn)時間の複雑さがかかります

注意:「ヒープソート」アルゴリズムの手順は次のとおりです。

すべての配列値をヒープに追加します: amortized-analysis トリックを使用してO(n)時間の複雑さに合計します
ヒープから最小値をn回ポップし、i番目の値を配列のi番目のインデックスに配置します。最小値をポップするときに償却分析トリックが機能しないため、O(nlogn) 時間の複雑さ

私の質問は:ヒープを空にするときに償却分析トリックが機能せず、ヒープソートアルゴリズムがO(nlogn)時間ではなくO (nlogn) 時間かかるのはなぜですか?

編集/回答

ヒープが配列に格納されている場合 (ポインターを持つ動的ツリーノードではなく)、ヒープをボトムアップで構築できます。つまり、リーフからルートまで開始し、償却分析を使用して合計時間の複雑さを取得できます。O(n)の、ヒープの最小値のボトムアップを空にすることはできません。

score 1 · Accepted Answer

任意の配列をヒープに変換し (これを「ヒープビルド」と呼びます)、それをヒープソートで並べ替える複雑さを計算する方法を「数学的に」示しましょう。

配列をヒープに変換するには、子を持つ各ノードを見て、そのノードを「ヒープ化」(シンク) する必要があります。実行する比較の数を自問する必要があります。考えてみると、次のことがわかります (h = 木の高さ):

レベル i の各ノードに対して、hi 比較を行います: #comparesOneNode(i) = hi
レベル i には、2^i ノードがあります: #nodes(i) = 2^i
したがって、一般に T(n,i) = #nodes(i) * #comparesOneNode(i) = 2^i *(hi) は、レベル「i」での「比較」に費やされた時間です。

例を挙げましょう。15 要素の配列があるとします。つまり、ツリーの高さは h = log2(15) = 3 になります。

レベル i=3 では、2^3=8 個のノードがあり、ノードごとに 3 ～ 3 回の比較を行います。レベル 3 では、子を持たないノード、つまり葉しかないため、正解です。T(n, 3) = 2^3*(3-3) = 0
レベル i=2 では、2^2=4 個のノードがあり、ノードごとに 3-2 回の比較を行います。レベル 2 では比較できるレベル 3 しかないため、正解です。T(n, 2) = 2^2*(3-2) = 4 * 1
レベル i=1 では、2^1=2 個のノードがあり、各ノードに対して 3-1 回の比較を行います: T(n, 1) = 2^1*(3-1) = 2 * 2
レベル i=0 では、ルートである 2^0=1 ノードがあり、3-0 比較を行います: T(n, 0) = 2^0*(3-0) = 1 * 3

わかりました、一般的に：

T(n) = sum(i=0 ～ h) 2^i * (hi)

しかし、h = log2(n) を覚えていれば、

T(n) = sum(i=0 から log2(n)) 2^i * (log2(n) - i) =~ 2n

さて、ここでの分析は非常に似ています。最大要素 (ルート) を「削除」するたびに、ツリーの最後のリーフをルートに移動し、それをヒープ化し、最後まで繰り返します。では、ここで実行する比較の数は?

レベル i には、2^i ノードがあります: #nodes(i) = 2^i
レベル「i」の各ノードに対して、最悪の場合、heapify は常にレベル「i」とまったく同じ数の比較を行います (レベル i から 1 つのノードを取得し、それをルートに移動し、heapify を呼び出します)。、最悪の場合、heapify はノードをレベル i に戻し、"i" 比較を実行します): #comparesOneNode(i) = i
したがって、一般に T(n,i) = #nodes(i) * #comparesOneNode(i) = 2^i*i は、最初の 2^i のルートを削除し、一時的なルートを正しい位置に戻すために費やされた時間です。 .

例を挙げましょう。15 要素の配列があるとします。つまり、ツリーの高さは h = log2(15) = 3 になります。

レベル i=3 では、2^3=8 個のノードがあり、それぞれをルートの場所に移動してから、それぞれをヒープ化する必要があります。ルートがまだ存在するレベル "i" に沈む可能性があるため、各 heapify は最悪の場合の "i" 比較で実行されます。T(n, 3) = 2^3 * 3 = 8*3
レベル i=2 では、2^2=4 ノードがあり、ノードごとに 2 つの比較を行います: T(n, 2) = 2^2*2 = 4 * 2
レベル i=1 では、2^1=2 ノードがあり、ノードごとに 1 つの比較を行います: T(n, 1) = 2^1*1 = 2 * 1
レベル i=0 では、ルートである 2^0=1 ノードがあり、0 の比較を行います: T(n, 0) = 0

わかりました、一般的に：

T(n) = sum(i=0～h) 2^i * i

しかし、h = log2(n) を覚えていれば、

T(n) = sum(i=0 から log2(n)) 2^i * i =~ 2nlogn

直観的に、ヒープソートはコストを「償却」できないことがわかります。これは、ノード数を増やすたびに比較を行う必要があるためです。ヒープビルド機能は正反対です。ここで見ることができます：

そう：