【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら
6-8 ヒープソート
ヒープ
ヒープとは、親の値が子の値以上であるという条件を満たす完全2分木です。(どの親子に対しても、親の値より子の値の方が小さくなる。)
ヒープソート
ヒープソートは、最大値が根に位置することを利用してソートを行うアルゴリズムです。
具体的には
・ヒープから最大値である値を取り出す。
・根以外の部分をヒープ化する。
という作業を繰り返します。
ヒープソートは、選択ソートの応用的なアルゴリズムです。
#根を削除したヒープの再構築
根を削除して再ヒープ化するために、要素を適切な位置へと下していく手続きをまとめると、
1．根を取り出す。
2．最後の要素(最下流の最も右側に位置する要素)を根に移動する。
3．自身より大きい方の子と交換して一つの下流に下りる作業を、根から始めて以下の条件のいずれか一方が成立するまで繰り返す。
・子の方が値が小さい
・葉に到達した
#ヒープソートへの拡張
次はヒープソート自体のアルゴリズムです。
1．変数iの値をn-1で初期化する。
2．a[0]とa[i]を交換する
3．a[0],a[1],・・・a[i - 1]をヒープ化する
4．iの値をデクリメントして0になれば終了。そうでなければ2に戻る。
子の手順によってソートが行えます。
ここで、配列の初期状態がヒープの要件を見たしているという保証がないということが抜けています。そのため、この手続きをする前に配列をヒープ化する必要があります。
配列のヒープ化
下流の小さい部分木からボトムアップ的に積み上げれば、配列のヒープ化が可能です。
最下流の右側から始めて左側へと進んでいき、そのレベルが終了したら一つ上流側へと移動しながら部分木をヒープ化していきます。
#ヒープソート
from typing import MutableSequence
def heap_sort(a: MutableSequence) -> None:
"""ヒープソート"""
def down_heap(a: MutableSequence, left: int, right: int) -> None:
"""a[left]～a[right]をヒープ化"""
temp = a[left] #根
parent = left
while parent < (right + 1) // 2:
cl = parent * 2 + 1 #左の子
cr = cl + 1 #右の子
child = cr if cr <= right and a[cr] > a[cl] else cl #大きい方
if temp >= a[child]:
break
a[parent] = a[child]
parent = child
a[parent] = temp
n = len(a)
for i in range((n - 1) // 2, -1, -1): #a[i] ～a[n - 1]をヒープ化
down_heap(a, i, n - 1)
for i in range(n - 1, 0, -1):
a[0], a[i] = a[i], a[0] #最大要素と未ソート部末尾要素を交換
down_heap(a, 0, i - 1)
if __name__ == '__main__':
print('ヒープソート')
num = int(input('要素数：'))
x = [None] * num #要素数numの配列を生成
for i in range(num):
x[i] = int(input(f'x[{i}]：'))
heap_sort(x) #配列xをヒープソート
print('昇順にソートしました。')
for i in range(num):
print(f'x[{i}]={x[i]}')
関数down_heap
配列a中のa[left]～a[right]の要素をヒープ化する関数です。先頭要素であるa[left]以外はヒープ化されているという前提に基づいてa[left]を下流の適切な位置まで下ろすことでヒープ化を行います。
関数heap_sort
要素数nの配列aをヒープソートする関数です。
1．関数down_heapを利用して配列aをヒープ化します。
2．最大値である根すなわちa[0]を取り出して、配列の末尾側と交換し、配列の部分えお再ヒープ化する手続きを繰り返すことでソートを行います。
# ヒープソートの時間計算量
選択ソートの応用的アルゴリズムであるヒープソートの計算量はO(n log n)です。(単純選択ソートはO(n**2))
| heapqモジュールを用いたヒープソート |
|---|
heapモジュールでは、ヒープに対してプッシュを行うheappush関数とヒープからのポップを行うheappop関数が提供されます。これを利用することで簡潔に実現できます。
def heap_sort(a: MutableSequence) -> None:
"""ヒープソート(heapq.pushとheapq.popを利用)"""
heap = []
for i in a:
heapq.heappush(heap, i)
for i in range(len(a)):
a[i] = heapq.heappop(heap)
6-9 度数ソート
度数ソートは比較の必要がないことが特徴です。
step1：度数分布表の作成
イメージとしては配列aに格納されている数字を別の格納先の配列fの添字とリンクさせ、その数字が何個あるかカウントします。
a[5,7,0,2,4,10,3,1,3]
f[1,1,1,2,1,1,0,1,0,0,1]：aに3が2つあるため、f[3]は2になります。
step2：累積度数分布表の作成
0点からとある数字までに何個の数字があるかを表す分布表を作成します。
一つ手前の要素を足すことで実現できます。
結果として
[1,2,3,5,6,7,7,8,8,8,9,9]
となります。
step3：各数字が何番目に位置するか判明したため、a,fそれぞれの配列からソート済みの配列を作ります。ただしその作業には配列aと同じ要素数をもった作業用の目的配列が必要で、ここではbとします。b[f[a[i]]] = a[i]となります。
step4：配列のコピー
ソートが完了してもソート結果が格納されている作業用の配列はbであって、配列aは未ソートなため、配列bの全要素を配列aにコピーし直します。
# 度数ソート
from typing import MutableSequence
def fsort(a: MutableSequence, max: int) -> None:
"""度数ソート（配列要素の値は0以上max以下"""
n = len(a)
f = [0] * (max + 1) #累積度数
b = [0] * n #作業目的配列
for i in range(n): f[a[i]] += 1 #[step 1]
for i in range(1, max + 1): f[i] += f[i - 1] #[step 2]
for i in range(n - 1, -1, -1):f[a[i]] -= 1; b[f[a[i]]] = a[i] #[step 3]
for i in range(n): a[i] = b[i] #[step 4]
def counting_sort(a:MutableSequence) -> None:
"""度数ソート"""
fsort(a, max(a))
if __name__ == '__main__':
print('度数ソート')
num = int(input('要素数：'))
x = [None] * num #要素数numの配列を生成
for i in range(num):
while True:
x[i] = int(input(f'x[{i}]：'))
if x[i] >= 0: break
counting_sort(x) #配列xをヒープソート
print('昇順にソートしました。')
for i in range(num):
print(f'x[{i}]={x[i]}')
度数ソートは度数分布表が必要なため、整数値のみを取り得るテストの点数のようにデータの最小値と最大値があらかじめわかっている場合にしか適用できません。
また、配列の要素を飛び越えることがないため安定したアルゴリズムとなります。
以上で6章が終了しました。
ありがとうございました。