ヒープソートについて
- 計算量はOlog(n)
- ヒープを構成する分を含めると計算量はO(nlogn)となる
- ヒープは木構造で表される
- 2分木構造のヒープは2分ヒープと呼ばれる
- ヒープの子ノードは常に親ノードと同じか大きい
- 左詰めで構成される
- 子ノードの大小に制約はなし
- ヒープをリストで構成するとき、左側の子ノードは親ノードのインデックスの2倍+1、右側の子ノードは親ノードのインデックスの2倍+2で表される
コード
1 2 3 4 5 6 7 8 9 |
import heapq #heapqライブラリをインポート def heap_sort(array): h = array.copy() heapq.heapify(h) #heapqライブラリ内のheapify関数でヒープを構成 return [heapq.heappop(h) for _ in range(len(array))] data=[6,15,4,2,8,5,11,9,7,13] print(heap_sort(data)) |
参考
こちらの書籍を参考にしています。
ライブラリを用いたヒープソートの実装について確認しましたが、書籍の中ではヒープソートの実装を行うまでの前提として、スタック、キュー、heapify関数の内容について解説されています。
特にライブラリを用いると、実際の動作はブラックボックスのような状態になります。
書籍でheapify関数についてコードが記載されているので、確認することでヒープソートの理解をより深められるかと思います。
コメント