minheapからの削除の平均時間複雑度

Question

ヒープ上のすべての要素を削除するための平均複雑度（つまり、最小ヒープ上のremoveMin）

Answer 1

質問は本質的にヒープソープに関するものです.minヒープを作成して、一度に1つずつ要素を削除して並べ替えられたリストを生成します。最小ヒープの構築はO（N）であり、このコストは要素を抽出するコストによって支配されることになる。

ヒープソースの抽出フェーズの最悪のケースは比較的簡単です。それぞれの除去はO（log N）であり、N個であるため、複雑さはO（N log N）でなければなりません。

これは平均がO（N log N）であることを意味しません。そのためには、より困難なことを示すためにはLower bound on heapsort?が必要です。つまり、抽出フェーズの最適なケースの複雑さもTheta（N log N）です。

平均値は、最良（Θ（N log N））ケースと最悪（O（N log N））ケースの間でなければならず、したがってシータ（N log N）もそうでなければならない。