この記事について
この記事では筆者が『アルゴリズム図鑑』を読んで学んだアルゴリズムについて、Python3での実装例を紹介したいと思います。今回のアルゴリズムはヒープソートです。筆者は素人です。色々教えていただけると幸いです。
筆者はPython2のことをよく知りませんが、自分がPython3を使ってるっぽいことだけはわかっています(Python3.6.0かな？)。そのため、記事のタイトルではPython3としました。
ヒープソートについて
問題設定とアプローチについてざっくりとだけ説明します。「ヒープ」というデータ構造を使います。ヒープについて詳しくは『アルゴリズム図鑑』を参照ください。
問題
与えられた数の列に対して、小さい数から順に並べ替えた列を返す。
例：
5, 2, 7, 3, 6, 1, 4
→ 1, 2, 3, 4, 5, 6, 7
アプローチ
与えられた数を降順ヒープ(根が最大)に格納し、「根から値をとる→一番左に置く」を繰り返す。詳細は『アルゴリズム図鑑』を参照。
実装コードと実行結果
実装したコードを以下に示します。最初に少し考え方を説明します。
なお、勉強のためあえて実装してみましたが、Python では標準ライブラリで heapq というモジュールが用意されているようなので、実用的にはそれを使うといいと思います( https://docs.python.org/ja/3/library/heapq.html )。
考え方
配列の要素の順番に意味を想定して、ヒープというデータ構造を実現します。『アルゴリズム図鑑』のヒープソートの項の補足を見ていただければわかりやすいかと思います。
また、ヒープ(2分ヒープ)では要素の番号を1から始めると便利なのでそのようにします(Wikipedia 二分ヒープ#ヒープの実装)。
ざっくり言うと下記のような感じ。
- 配列 heap に値を格納していく
- heap[0] は無視する(ダミーの値を入れておく)
- heap[1] が根
- heap[2]とheap[3]はheap[1]の子、heap[4]とheap[5]はheap[2]の子、heap[6]とheap[7]はheap[3]の子、...
コード
最初に変数dataに代入されているリストが処理対象の数の列です。
あと、このコードはわかりにくいかもしれないので、いくつか関数を定義して見通しがよくなった(?)バージョンのコードを、補足として最下部に記載します。どちらがいいかご意見いただければ幸いです。
data = [5, 2, 7, 3, 6, 1, 4]
print("input :" + str(data))
data_len = len(data)
heap = [0] #第0要素はダミー(ヒープでは1から数えると計算しやすい)
#入力されたデータを順にヒープに格納する(ヒープは都度再構築する)
for i in range(0, data_len):
heap.append(data[i])
if i > 0:
child = i + 1
parent = child // 2
while(heap[parent] < heap[child]):
heap[parent], heap[child] = heap[child], heap[parent]
if parent > 1:
child = parent
parent = child // 2
else:
#根まで達しているので、ここで抜ける
break
#ヒープの根から値を取り出していく(ヒープは都度再構築する)
output_data = list() #出力用の配列
for i in range(0, data_len):
#根の値をコピー
output_data.insert(0, heap[1])
#根の値を削除し、ヒープを再構築
heap[1] = heap[-1]
heap.pop(-1)
parent = 1
while(len(heap) >= 2 * parent + 1):
if len(heap) == 2 * parent + 1:
if heap[parent] < heap[2 * parent]:
heap[parent], heap[2 * parent] = heap[2 * parent], heap[parent]
#これより先、枝はないので抜ける
break
else:
if heap[2 * parent] > heap[2 * parent + 1]:
child = 2 * parent
else:
child = 2 * parent + 1
if heap[parent] < heap[child]:
heap[parent], heap[child] = heap[child], heap[parent]
parent = child
else:
break
print("output :" + str(output_data))
実行結果
$ python heap_sort.py
input :[5, 2, 7, 3, 6, 1, 4]
output :[1, 2, 3, 4, 5, 6, 7]
終わりに
気づいた点などあればご指摘、ご質問いただければと思います。特にコードの書き方の改善点などあれば勉強になるなと思います。
また実装コードのテストや他のアルゴリズムとの速さ比較についてヒント等いただければ幸いです。(ろくにテストしていません(^^;)
補足
上記のコードで、いくつか関数を定義して見通しがよくなった(?)バージョンのコードです。
def parent_of(child):
return child // 2
def left_child_of(parent):
return 2 * parent
def right_child_of(parent):
return 2 * parent + 1
def heap_size(heap):
return len(heap[1:])
data = [5, 2, 7, 3, 6, 1, 4]
# data = [43, 1, -4, 91, 46, -609]
print("input :" + str(data))
data_len = len(data)
heap = [0] #第0要素はダミー(ヒープでは1から数えると計算しやすい)
#入力されたデータを順にヒープに格納する(ヒープは都度再構築する)
for i in range(0, data_len):
heap.append(data[i])
if i > 0:
child = i + 1
parent = parent_of(child)
while(heap[parent] < heap[child]):
heap[parent], heap[child] = heap[child], heap[parent]
if parent > 1:
child = parent
parent = parent_of(child)
else:
#根まで達しているので、ここで抜ける
break
#ヒープの根から値を取り出していく(ヒープは都度再構築する)
output_data = list() #出力用の配列
for i in range(0, data_len):
#根の値をコピー
output_data.insert(0, heap[1])
#根の値を削除し、ヒープを再構築
heap[1] = heap[-1]
heap.pop(-1)
parent = 1
while(heap_size(heap) >= left_child_of(parent)):
if heap_size(heap) == left_child_of(parent):
child = left_child_of(parent)
if heap[parent] < heap[child]:
heap[parent], heap[child] = heap[child], heap[parent]
#これより先、枝はないので抜ける
break
else:
if heap[left_child_of(parent)] > heap[right_child_of(parent)]:
child = left_child_of(parent)
else:
child = right_child_of(parent)
if heap[parent] < heap[child]:
heap[parent], heap[child] = heap[child], heap[parent]
parent = child
else:
break
print("output :" + str(output_data))