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

Python

2021.08.28

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

ヒープソートについて
コード
参考

ヒープソートについて

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

コード

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))

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関数についてコードが記載されているので、確認することでヒープソートの理解をより深められるかと思います。