ヒープソートのBUILD-MAX-HEAPの実行時間がO(n)であることがわかりました。しかし、配列が降順でソートされている場合、なぜBUILD-MAX-HEAPの実行時間はO(n)になるのでしょうか？
O(1)のようなものではないですか？すでに最大値から最小値にソートされているため、MAX-HEAPIFYは必要ありません。配列のBUILD-MAX-HEAP実行時間が降順でソート
私の理解は正しいですか？誰かがそれを私に説明してもらえますか？
あなたは正しいです。もちろんO(1)でもかまいません。あなたのリストがソートされていることが分かっているときは、それを最大のヒープとして使うことができます。
アレイを使用してヒープの一般的な実装は、その要素の位置は、この動作を使用して：
childs[i] = 2i+1 and 2i+2
parent[i] = floor((i-1)/2)
このルールは、ソートされた配列に適用されます。 （最大ヒープの場合は降順、最小ヒープの場合は増加）。
注記最初にリストがソートされていることを確認する必要がある場合は、それでももちろんO(n)です。
EDIT：ヒープソート複雑
配列をソートする可能性があり、ヒープを構築することは、実際にO(1)がかかる場合がありますにもかかわらず 。ヒープソートを実行するたびに、最終的にはO(n log n)になります。
ヒープソートでは、extract-maxをnと呼びます。各抽出操作には、O(log n)が必要です。合計時間複雑度はO(n log n)になります。
配列がソートされていない場合、O(n + nlogn)の合計時間複雑度はまだO(n log n)です。
が既にであることが分かっている場合、配列は既に降順でソートされています。ソートする必要はありません。昇順にしたい場合は、O（n）時間に配列を逆にすることができます。
配列がすでにソートされているかどうかわからない場合は、すでに逆ソートされているかどうかを判断するためにO（n）が必要です。
リバースソートされた配列から最大ヒープを構築する理由は、アイテムn/2で開始し、要素をその子要素より小さくしていないことを確認しなければならないということです。実行される操作の数はチェックされる項目の総数に比例するため、n/2個のチェックしかないのにO（n）とみなされます。
リバースソートされた配列からmax-heapを作成することは、配列を逆順でソートするかどうかを確認するよりも速いことに注意してください。
ありがとうございます。 しかし、なぜBUILD-MAX-HEAPに 'O（1）'という時間がかかるにもかかわらず、ヒープソートは 'O（n lg n）'の実行時間を持っています。 なぜそれが 'O（lg n）' = 'O（lg n）'ではないのですか？ – mskeira
@mskeiraヒープ・ソートを実行する時間は、* n *回のextract-max呼び出しによって支配されるため、ヒープが最初から完全にソートされていても** log ** * n *時間がかかります。 「ほとんどソートされた」入力に対してより良いパフォーマンスを発揮するヒープソートのいくつかの変形実装があります。 – rici
@mskeira私はそれに応じて私の答えを編集しましたが、質問の範囲外です。この答えが正しいと分かったら、私の答えの横にある* V *をクリックして受け入れてください。喜んで助けてください。 –