【Python】ヒープソート【アルゴリズム】

この記事は約1分で読めます。

ヒープソートについて

  • 計算量はOlog(n)
  • ヒープを構成する分を含めると計算量はO(nlogn)となる
  • ヒープは木構造で表される
  • 2分木構造のヒープは2分ヒープと呼ばれる
  • ヒープの子ノードは常に親ノードと同じか大きい
  • 左詰めで構成される
  • 子ノードの大小に制約はなし
  • ヒープをリストで構成するとき、左側の子ノードは親ノードのインデックスの2倍+1、右側の子ノードは親ノードのインデックスの2倍+2で表される

コード

 

参考

こちらの書籍を参考にしています。

ライブラリを用いたヒープソートの実装について確認しましたが、書籍の中ではヒープソートの実装を行うまでの前提として、スタック、キュー、heapify関数の内容について解説されています。

特にライブラリを用いると、実際の動作はブラックボックスのような状態になります。

書籍でheapify関数についてコードが記載されているので、確認することでヒープソートの理解をより深められるかと思います。

コメント