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

初心者向けにPythonのheapqモジュールの使い方について解説しています。優先度付きキューheapqの仕組みと使い方についてサンプルプログラムを動かしながら学習しましょう。実際にソースコードを書いているので、ぜひ参考にしてみてください。

TechAcademyマガジンはオンラインのプログラミングスクールTechAcademy [テックアカデミー]が運営する教育×テクノロジーのWebメディアです。初心者でもすぐ勉強できる記事が2,000以上あります。

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

Pythonについてそもそもよく分からないという方は、Pythonとは何なのか解説した記事をまずご覧ください。

 

なお本記事は、TechAcademyのPythonオンライン講座の内容をもとにしています。

 

田島悠介

今回は、Pythonに関する内容だね!

大石ゆかり

どういう内容でしょうか?

田島悠介

heapqモジュールの使い方について詳しく説明していくね!

大石ゆかり

お願いします!

 

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] Pythonで挫折しない学習方法を動画で公開中

実際に書いてみよう

今回のサンプルプログラムでは、公式ドキュメントのソースを参考に、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を使って機械学習の基礎を学ぶPythonオンライン講座を開催しています。

初心者向けの書籍を使って人工知能(AI)や機械学習について学ぶことができます。

現役エンジニアがパーソナルメンターとして受講生に1人ずつつき、マンツーマンのメンタリングで学習をサポートし、最短4週間で習得することが可能です。

また、現役エンジニアから学べる無料のプログラミング体験会も実施しているので、ぜひ参加してみてください。