[python標準ライブラリ]heapq-スタックソートアルゴリズム

[Python標準ライブラリ]heapq-スタックソートアルゴリズムの役割:headpqモジュールはPythonリストに適した最小スタックソートアルゴリズムを実現した.Pythonバージョン:2.3バージョンに追加され、2.5バージョンで補完スタック(heap)が作成されたツリーデータ構造で、サブノードと親ノードは秩序関係にあります.二重フォークスタック(Binary heap)は、要素Nのサブ要素が2*N+1および2*N+2(インデックスが0から始まる)に位置するように構成されたリストまたは配列で表すことができる.このレイアウトでは、要素を追加または削除するときに大量のメモリを割り当てる必要がなく、スタックをその場で再編成できます.最大スタック(max-heap)は、親ノードが2つのサブノード以上であることを確認します.最小スタック(min-heap)は、親ノードが子ノード以下であることを要求する.Pythonのheapqモジュールは最小スタックを実現した.サンプルデータの例ではheapq_が使用されます.heapdata.pyのデータ.

# This data was generated with the random module.

data = [19, 9, 4, 10, 11]

ヒープ出力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('
')
        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つの基本的な方法があります.

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)

       
heappush()を使用すると、データソースから新しい要素を追加するときに要素のスタック順序が維持されます.
データがすでにメモリに存在する場合は、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)

リストをスタック順に1つの要素で構築すると、無秩序リストを構築してheapify()を呼び出すのと同じ結果が得られます.
アクセススタックの内容
スタックが正しく整理されると、heapppop()を使用して最小値の要素を削除できます.

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

for i in xrange(2):
    smallest = heapq.heappop(data)
    print 'pop    %3d:' % smallest
    show_tree(data)

1つの操作で既存の要素を削除して新しい値に置き換える場合は、heapeplace()を使用します.

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, 13]:
    smallest = heapq.heapreplace(data, n)
    print 'replace %2d with %2d:' % (smallest, n)
    show_tree(data)

要素をその場で置き換えることで、優先順位でソートされたジョブキューなどの固定サイズのスタックを維持できます.
スタックのデータ極値
heapqはまた、反復可能なオブジェクトを検査する2つの関数を含み、その中に含まれる最大値または最小値の範囲を検索する.

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]

n値(n>1)が相対的に小さい場合にのみnlargest()とnsmallest()を使用すると効率的ですが、この2つの関数が便利になる場合があります.