Pythonのheapqモジュールの使い方【初心者向け】

Pythonのheapqモジュールの使い方について解説します。

そもそもPythonについてよく分からないという方は、Pythonとは何なのか解説した記事を読むとさらに理解が深まります。

 

なお本記事は、TechAcademyのオンラインブートキャンプPython講座の内容をもとに紹介しています。

 

 

heapqモジュールとは

heapqモジュールは、 Python でヒープキューアルゴリズムの実装を提供しているモジュールです。ヒープキューアルゴリズムは、優先度キューアルゴリズムとしても知られています。

キューとは複数の要素が並んだものです。優先度キューとは、ある優先度に従い要素を取り出す仕組みを持ったキューです。ヒープキューとは優先度キューのアルゴリズムの1つで、全ての親の値が、その全ての子の値以下であるようなツリー構造になっており、その構造を生かして効率的に要素を取り出すことができます。

ヒープキューは効率的なソート(並べ替え)の手法であるヒープソートとして広く利用されて来ました。一般的に要素数が増えるとソートには時間がかかります。

例えば単純に全ての値の大小を比較しながら並べ替えるソート(バブルソート)の場合、要素数の2乗に比例した計算量(要素数をNとした場合、 O(N^2) )を要します。それに対してヒープソートは、要素数×Log(要素数)以内の計算量( O(N LogN) )であることが計算上確認されています。また全ての要素を確認しなくても親子関係だけでソートを行えるため、巨大なデータのソートに対しても効率的です。

heapqモジュールは Python の標準モジュールです。用意されているメソッドなど、詳細は公式ドキュメントを参考にしてください。

https://docs.python.jp/3/library/heapq.html

 

heapqモジュールの使い方

heapqモジュールを使うには、モジュールをインポートします。

import heapq

ヒープキューに値を追加するには heappush メソッドを使います。

heapq.heappush(heap, item)

またヒープキューから値を取り出すには heappop メソッドを使います。

heapq.heappop(heap)

 

[PR] 未経験からWebエンジニアを目指す方法とは

実際に書いてみよう

今回のサンプルプログラムでは、公式ドキュメントのソースを参考に、heapqモジュールの使い方を確認します。以下のソースを入力して、heapqtest.py という名前で保存してください。

import heapq

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])

入力が終わったら実行してみましょう。

python heapqtest.py

実行結果は以下のようになります。

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

ヒープキューアルゴリズムを利用してソートされた結果が表示されました。

 

この記事を監修してくれた方 太田和樹（おおたかずき） ITベンチャー企業のPM兼エンジニア 普段は主に、Web系アプリケーション開発のプロジェクトマネージャーとプログラミング講師を行っている。守備範囲はフロントエンド、モバイル、サーバサイド、データサイエンティストと幅広い。その幅広い知見を生かして、複数の領域を組み合わせた新しい提案をするのが得意。 開発実績：画像認識技術を活用した駐車場混雑状況把握（実証実験）、音声認識を活用したヘルプデスク支援システム、Pepperを遠隔操作するアプリの開発、大規模基幹系システムの開発・導入マネジメント 地方在住。仕事のほとんどをリモートオフィスで行う。通勤で消耗する代わりに趣味のDIYや家庭菜園、家族との時間を楽しんでいる。

 

 

TechAcademyでは、初心者でもPythonを使った人工知能（AI）や機械学習の基礎を習得できるオンラインブートキャンプPython講座を開催しています。

挫折しない学習方法を知れる説明動画や、現役エンジニアとのビデオ通話とチャットサポート、学習用カリキュラムを体験できる無料体験も実施しているので、ぜひ参加してみてください。