は、すべての要素が

Question

同一であり、ヒープ・ソートの時間を、実行している私たちは、すべての要素がサイズの配列Aに同一であり、nはヒープの並べ替えの時間を実行するとO（n）の

あるとき、と言うことができますすべての要素が等しい場合、ヒープはO（n）ステップを要します。ヒープマップの実行時間は、O（n）の最長実行時間です。

Answer 1

1つの比較O（1）後にヒープに要素が追加されると、正しい位置にあることがわかります。

ルートを削除することもO（1）です。テールとルートを入れ替えると、ヒーププロパティはまだ満たされます。

すべての要素はO（n）のヒープに追加され、O（n）では削除されます。だから、のこのケースヒープソートはO（n）です。私はより良いケースを考えることができないので、ヒープソースのベストケースはO（n）でなければなりません。

'Heapsorts best case is O（n）'は英語のような意味です：heapsortが最大でk * n必要なサイズの配列が存在します。それは理論的にはいいですが、実際には、それがどれくらい良いか速いかについてはあまり言いません。