heapq – インプレースヒープソートアルゴリズム¶
| 目的: | heapq は Python のリストで使用し易い最小ヒープソートアルゴリズムを実装します |
|---|---|
| 利用できるバージョン: | 2.3 で新規追加、2.5 で機能拡張されています |
ヒープ は子ノードがその親とソートされた関係を持つ木(ツリー)のようなデータ構造です。 バイナリヒープ は、要素 N の子どもが 2*N+1 や 2*N+2(ゼロから始まるインデックス) に配置されるようにリスト又は配列で構成されます。この構造は配置済みのヒープに対して再配置することを可能にします。そのため、要素を追加したり削除したりするときに多くのメモリの再割当が必要ではありません。
最大ヒープは親がその子どもの両方と等価、又は大きいことを保証します。最小ヒープは親がその子どもと等価、又は小さくなるのを要求します。Python の heapq モジュールは最小ヒープを実装します。
サンプルデータ¶
このサンプルデータを用いた例を次に示します。
# このデータは random モジュールで生成されました
data = [19, 9, 4, 10, 11, 8, 2]
ヒープの出力は heapq_showtree.py を使用して表示されます。
import math
from cStringIO import StringIO
def show_tree(tree, total_width=36, fill=' '):
"""Pretty-print a tree."""
output = StringIO()
last_row = -1
for i, n in enumerate(tree):
if i:
row = int(math.floor(math.log(i+1, 2)))
else:
row = 0
if row != last_row:
output.write('\n')
columns = 2**row
col_width = int(math.floor((total_width * 1.0) / columns))
output.write(str(n).center(col_width, fill))
last_row = row
print output.getvalue()
print '-' * total_width
print
return
ヒープを作成する¶
ヒープを作成する基本的な方法として heappush() と heapify() の2つの方法があります。
heappush() を使用すると、その要素のヒープソートの順序はデータソースから追加された新たなアイテムとして保たれます。
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data
heap = []
print 'random :', data
print
for n in data:
print 'add %3d:' % n
heapq.heappush(heap, n)
show_tree(heap)
$ python heapq_heappush.py
random : [19, 9, 4, 10, 11, 8, 2]
add 19:
19
------------------------------------
add 9:
9
19
------------------------------------
add 4:
4
19 9
------------------------------------
add 10:
4
10 9
19
------------------------------------
add 11:
4
10 9
19 11
------------------------------------
add 8:
4
10 8
19 11 9
------------------------------------
add 2:
2
10 4
19 11 9 8
------------------------------------
対象のデータが既にメモリ上にあるなら、配置済みリストのアイテムを再配置するために heapify() を使用する方が効率的です。
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data
print 'random :', data
heapq.heapify(data)
print 'heapified :'
show_tree(data)
$ python heapq_heapify.py
random : [19, 9, 4, 10, 11, 8, 2]
heapified :
2
9 4
10 11 8 19
------------------------------------
ヒープの要素にアクセスする¶
1度ヒープが正しく構成されると、最小値の要素を削除するために heappop() を使用します。標準ライブラリドキュメントで説明されている例では heapify() と heappop() が数値のリストをソートするために使用されています。
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data
print 'random :', data
heapq.heapify(data)
print 'heapified :'
show_tree(data)
print
inorder = []
while data:
smallest = heapq.heappop(data)
print 'pop %3d:' % smallest
show_tree(data)
inorder.append(smallest)
print 'inorder :', inorder
$ python heapq_heappop.py
random : [19, 9, 4, 10, 11, 8, 2]
heapified :
2
9 4
10 11 8 19
------------------------------------
pop 2:
4
9 8
10 11 19
------------------------------------
pop 4:
8
9 19
10 11
------------------------------------
pop 8:
9
10 19
11
------------------------------------
pop 9:
10
11 19
------------------------------------
pop 10:
11
19
------------------------------------
pop 11:
19
------------------------------------
pop 19:
------------------------------------
inorder : [2, 4, 8, 9, 10, 11, 19]
1回の操作で既存の要素を削除して新しい値をヒープに配置するには heapreplace() を使用してください。
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data
heapq.heapify(data)
print 'start:'
show_tree(data)
for n in [0, 7, 13, 9, 5]:
smallest = heapq.heapreplace(data, n)
print 'replace %2d with %2d:' % (smallest, n)
show_tree(data)
配置済みの要素を置換する機能は、優先度で順序付けられたジョブキューのような固定長のヒープを保つのに役立ちます。
$ python heapq_heapreplace.py
start:
2
9 4
10 11 8 19
------------------------------------
replace 2 with 0:
0
9 4
10 11 8 19
------------------------------------
replace 0 with 7:
4
9 7
10 11 8 19
------------------------------------
replace 4 with 13:
7
9 8
10 11 13 19
------------------------------------
replace 7 with 9:
8
9 9
10 11 13 19
------------------------------------
replace 8 with 5:
5
9 9
10 11 13 19
------------------------------------
データの両端¶
heapq にはヒープに含まれる最小値や最大値の範囲を探すために繰り返し可能オブジェクトを調べる機能もあります。 nlargest() や nsmallest() を使用すると n > 1 の比較的小さい値の場合のみ本当に効率が良いですが、幾つかのケースでも役に立つことがあります。
import heapq
from heapq_heapdata import data
print 'all :', data
print '3 largest :', heapq.nlargest(3, data)
print 'from sort :', list(reversed(sorted(data)[-3:]))
print '3 smallest:', heapq.nsmallest(3, data)
print 'from sort :', sorted(data)[:3]
$ python heapq_extremes.py
all : [19, 9, 4, 10, 11, 8, 2]
3 largest : [19, 11, 10]
from sort : [19, 11, 10]
3 smallest: [2, 4, 8]
from sort : [2, 4, 8]
See also
- heapq
- 本モジュールの標準ライブラリドキュメント
- WikiPedia: Heap (data structure)
- ヒープのデータ構造の一般的な説明
- インメモリデータ構造
- その他の Python のデータ構造
- 優先キュー
- 標準ライブラリ Queue による優先度キューの実装
