[前回] アルゴリズムのモヤモヤをPythonで解消(5): マージソート
はじめに
Pythonでアルゴリズムを楽しむ、第6弾です。
今回のアルゴリズム: ヒープソート
問題
以下8つの数字を昇順で整列せよ。
8 4 3 7 6 5 2 1
解決案
ヒープソートを使用し、解決します。
その前に、理論知識のおさらいから。
データ構造: 木構造(きこうぞう、tree structure)
- 一つの要素(ノード)が複数の子要素を持ち、
- 一つの子要素が複数の孫要素を持ち、
- という形で階層が深くなるほど枝分かれしていく構造
- 一つの子要素が複数の孫要素を持ち、
- 節(ノード)
- 各要素(データ)
- 根でも葉でもないノードは節点
- 各要素(データ)
- 根(ルート)
- 最上位のノード
- 木構造に一つだけ存在
- 葉(リーフ)
- 最下位のノード
- 枝(ブランチ)
- 各ノードを関係づける線
データ構造: 2分木
- 子ノードの数を2個以下に限定した木構造
-
全2分木
- 子ノードの数が必ず2個
- 子ノードの数が必ず2個
-
完全2分木
- 根から葉までの全ての深さが同じか1つしか違わない
-
データ構造: ヒープ(heap)
- 下記制約を持つ木構造
- 子要素は親要素より常に大きいか等しい(または常に小さいか等しい)
データ構造: 二分ヒープ木
- 二分木を使って作られる、ヒープ構造の単純な種類のひとつ
- 二分木に、以下の2つの制約を追加したもの
- 要素間の順序関係に従った比較によって、各ノードはそのノードの子よりも小さいか等しくなるように配置される(heap property)
- 木は完全にバランスの取れた二分木(すべての葉は同じ深さにある)になるか、木のもっとも高い方がすべて埋まっていないならば、ノードは左から右へ順に埋まっていく(shape property)
ヒープソートとは
-
Wikipediaからヒープソート(heap sort)
- リストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズム
- ※ メモリ空間のヒープ領域とは無関係
- 計算量は、O($n\ log\ {n}$)
- 安定ソートではない
- データの出現順序による計算量の変化が小さい（クイックソートでは最悪の場合O($n^{2}$)となってしまう
- ただし、平均的にはクイックソートより遅い
- ソート対象のデータ自体以外に、必要作業領域の大きさは固定で、データ量に依存しない
- ただし、並列化できない
- ヒープ構造はメモリへのアクセスが連続しておらず、ランダムアクセスとなり、空間的局所性が低い
- 空間的局所性とは
- プロセッサがあるメモリー領域のコードを要求したとき、
- プロセッサが次に要求するのは、
- その次のメモリー領域や付近のメモリー領域である可能性が高いという性質
- 空間的局所性とは
- リストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズム
-
ヒープソートの計算量
- 最悪計算時間: O($n\ log\ {n}$)
- 最良計算時間: $\Omega(n)$
- 関数の下界を表すためのオーダー記号$\Omega$(オメガ)
- 平均計算時間: O($n\ log\ {n}$)
コード
Pythonのheapqモジュールを使用します。
heap_sort.py
from heapq import heappush
from heapq import heappop
import math
from io import StringIO
PRINT_WIDTH = 50
def print_heap(heap):
str_buf = StringIO()
last_level = -1
for idx, val in enumerate(heap):
if idx:
level = int(math.floor(math.log(idx + 1, 2)))
else:
level = 0
if level != last_level:
str_buf.write('\n')
col_num = 2 ** level
col_width = int(math.floor((PRINT_WIDTH * 1.0) / col_num))
str_buf.write(str(val).center(col_width, ' '))
last_level = level
print ('------------------------- 二分ヒープ木 -------------------------')
print (str_buf.getvalue())
print ('------------------------------------------------------------')
return
def heap_sort(arr):
heap = []
print('====================== ヒープソート開始 ======================')
print('初期値: ', end='')
print(arr)
for idx in range(len(arr)):
print('=> %dを配列から取り出し、ヒープに入れる' % arr[idx])
heappush(heap, arr[idx])
print_heap(heap)
print('配列: ', end='')
print(arr[idx + 1:])
new_arr = []
for idx in range(len(heap)):
popped = heappop(heap)
print('=> %dをヒープから取り出し、配列に入れる' % popped)
print_heap(heap)
new_arr.append(popped)
print('配列: ', end='')
print(new_arr)
print('====================== ヒープソート終了 ======================')
if __name__ == '__main__':
arr = [8, 4, 3, 7, 6, 5, 2, 1]
heap_sort(arr)
- 実行
$ python heap_sort.py
- 結果
- 配列の値を、二分ヒープ木に以下規則で配置してから、再度取り出すと、結果ソートされる
各ノードはその子ノードより小さい
- 配列の値を、二分ヒープ木に以下規則で配置してから、再度取り出すと、結果ソートされる
====================== ヒープソート開始 ======================
初期値: [8, 4, 3, 7, 6, 5, 2, 1]
=> 8を配列から取り出し、ヒープに入れる
------------------------- 二分ヒープ木 -------------------------
8
------------------------------------------------------------
配列: [4, 3, 7, 6, 5, 2, 1]
=> 4を配列から取り出し、ヒープに入れる <- 4が8よりちいさいためルートとなる
------------------------- 二分ヒープ木 -------------------------
4
8
------------------------------------------------------------
配列: [3, 7, 6, 5, 2, 1]
=> 3を配列から取り出し、ヒープに入れる <- 3が4,8よりちいさいためルートとなる
------------------------- 二分ヒープ木 -------------------------
3
8 4
------------------------------------------------------------
配列: [7, 6, 5, 2, 1]
=> 7を配列から取り出し、ヒープに入れる <- 7が、8の親ノード、3の子ノードとなる
------------------------- 二分ヒープ木 -------------------------
3
7 4
8
------------------------------------------------------------
配列: [6, 5, 2, 1]
=> 6を配列から取り出し、ヒープに入れる <- 6が、7の親ノート、3の子ノードとなる
------------------------- 二分ヒープ木 -------------------------
3
6 4
8 7
------------------------------------------------------------
配列: [5, 2, 1]
=> 5を配列から取り出し、ヒープに入れる <- 5が、4の子ノードとなる
(※ 二分ヒープ木のため深さのバランスを取りながら左から右へ埋めていく)
------------------------- 二分ヒープ木 -------------------------
3
6 4
8 7 5
------------------------------------------------------------
配列: [2, 1]
=> 2を配列から取り出し、ヒープに入れる
------------------------- 二分ヒープ木 -------------------------
2
6 3
8 7 5 4
------------------------------------------------------------
配列: [1]
=> 1を配列から取り出し、ヒープに入れる
------------------------- 二分ヒープ木 -------------------------
1
2 3
6 7 5 4
8
------------------------------------------------------------
配列: [] <- 配列が空になったので
=> 1をヒープから取り出し、配列に入れる <- 一番小さいルートを取り出す、1の子ノードがルートに
(※ 取り出すときも、二分ヒープ木の深さのバランスを取りながら位置調整する)
------------------------- 二分ヒープ木 -------------------------
2
6 3
8 7 5 4
------------------------------------------------------------
配列: [1]
=> 2をヒープから取り出し、配列に入れる
------------------------- 二分ヒープ木 -------------------------
3
6 4
8 7 5
------------------------------------------------------------
配列: [1, 2]
=> 3をヒープから取り出し、配列に入れる
------------------------- 二分ヒープ木 -------------------------
4
6 5
8 7
------------------------------------------------------------
配列: [1, 2, 3]
=> 4をヒープから取り出し、配列に入れる
------------------------- 二分ヒープ木 -------------------------
5
6 7
8
------------------------------------------------------------
配列: [1, 2, 3, 4]
=> 5をヒープから取り出し、配列に入れる
------------------------- 二分ヒープ木 -------------------------
6
8 7
------------------------------------------------------------
配列: [1, 2, 3, 4, 5]
=> 6をヒープから取り出し、配列に入れる
------------------------- 二分ヒープ木 -------------------------
7
8
------------------------------------------------------------
配列: [1, 2, 3, 4, 5, 6]
=> 7をヒープから取り出し、配列に入れる
------------------------- 二分ヒープ木 -------------------------
8
------------------------------------------------------------
配列: [1, 2, 3, 4, 5, 6, 7]
=> 8をヒープから取り出し、配列に入れる
------------------------- 二分ヒープ木 -------------------------
------------------------------------------------------------
配列: [1, 2, 3, 4, 5, 6, 7, 8]
====================== ヒープソート終了 ======================
おわりに
Pythonでヒープソートアルゴリズムを解いてみました。
次回も続きます。お楽しみに。