今回は、Pythonの重要なデータ構造であるヒープ（Pythonではヒープキューと呼ばれています）について学びます。
データ構造とその実装について学んだ後、同じ内容のPythonのコードを見ていきます。
この記事もチェック：PythonでMax Heapデータ構造を実装する方法
Pythonのヒープとは？
Pythonのヒープは完全な二分木で、各ノードはそのすべての子と等しいより小さいか等しいより大きいです（最大ヒープか最小ヒープかによってより小さいか大きいか決まります）。
したがって、ヒープのルートノードは最小または最大の要素です。
ヒープデータ構造は一般に優先度待ち行列を表現するために使われる。
一般に、ヒープには2つの形式がある。
- Min-Heap。最小ヒープは、すべてのノードがその子より小さいヒープです。ルートはミニヒープで最も低い値を持つ。
- マックス・ヒープ。マックスヒープ：すべてのノードがその子ノードより大きいヒープです。マックスヒープ：マックスヒープは、すべてのノードがその子ノードより大きいヒープです。
以下は、ミニヒープとマックスヒープの例です。
# The heap functionalities are in the heapq package, so import itimport heapq
# we now initialise a list to be converted to heap lis = [15, 7, 9, 4, 13]
# converting lis to heap using the heapify functionheapq.heapify(lis) print ("The heap looks like: ")
print(lis)
#using the heappop functionprint ("The popped item using heappushpop() is : ",end="")
print (heapq.heappop(lis))
print ("After popping, the heap looks like: ")
print(lis)
#using the heappush function to push 2print ("After pushing 2, the heap looks like: ")
heapq.heappush(lis, 2)
print(lis)
|
PythonのヒープはデフォルトではMin-heapであり、この記事ではヒープについて語るとき、Min-heapを考慮することにします。
では、実際にヒープデータ構造がどのように実装されているかを見てみましょう。
H
Pythonでヒープを実装するためのheapqモジュールを使う
Pythonにはヒープキュー（または単にヒープ）を実装するための “heapq “モジュールがあります。
このモジュールには、最小の要素が常に先頭にあり、pop関数が呼ばれたときにpopされるという機能が含まれています。
要素がpushまたはpopされるたびに、heapのプロパティは維持され、heap[0]は常に最小の関数を提供します。
本モジュールには、ヒープに関する以下の主要な関数が含まれる。
- heapify( iterable_name ): この関数は任意の反復子(例えばリスト)を渡して、それをヒープデータ構造に変換するために使用します。
- heappush( heap_name, element_to_be_inserted ): ヒープデータ構造に変換します。その名の通り、この関数はヒープに要素をプッシュ/追加します。ヒープ名と挿入される要素をパラメータとして渡す必要があります。この関数は、ヒーププロパティを満たすようにヒープを再配置します（必要であれば）。
- heappop( heap_name ): その名が示すように、この関数はパラメータとして渡されたヒープから要素をポップ/リムーブします。この関数は、ヒーププロパティを満たすために、(必要であれば)ヒープを再整理します。
Pythonヒープの実践的な実装
では、Pythonでミニヒープを実装してみましょう。
コードでは list [15, 7, 9, 4, 13] を使い、heapify 関数でヒープに変換します。
作られたヒープは次のようになります。
The heap looks like: [4, 7, 9, 15, 13]
The popped item using heappop() is : 4
After popping, the heap looks like: [7, 13, 9, 15]
After pushing 2, the heap looks like:
[2, 7, 9, 15, 13]
|
Pythonでのヒープの実装
結果は以下の通りです。
ここでは、heapq パッケージが待ち行列を作成し、要素をプッシュしたりポップしたりする機能を提供していることがわかります。
プッシュやポップの後、出力に見られるように、ヒープは自動的に並べ替えられます。
まとめ
この記事では、Pythonのヒープの概念について学びました。
Python の max-heap と min-heap とは何か、そしてそれらがどのように表現されるかを学びました。
さらに、 heapify, heappush, heappop 関数を使って Python で実装してみました。
今後も有益な記事をお届けする予定です。