[python]HIPデータ構造/heapq

最近、就職のためのコードテストwith Pythonが2019年にKakao Greedyアルゴリズムの問題を解いた際、優先度Qライブラリが分からなかったため、非常に困難な経験がありました.
今回のリリースでは、heapデータ構造とPythonのheapqモジュールの使用方法について説明します.

入る前に。

≪優先キュー|Priority Queue|emdw≫:優先度の概念をキューのデータ構造に導入します.
データ優先、優先度の高いデータ優先.
優先順位キューは、リストの並べ替え、接続、hipによって実現できます.その中でhipで実現するのが最も有効である.(挿入と削除はいずれもO(logn))

お尻って何?

hipは特定のルールを持つツリーであり,基本的には最値と最切り上げを迅速に検索するために設計された完全バイナリツリーである.
hip-property:AがBの親ノードである場合、Aのキー値とBのキー値との間にサイズ関係が確立されます.

最小ヒープ:親ノードのキー値は常に子ノードのキー値より小さい.

最大ヒープ:親ノードのキー値は常に子ノードのキー値より大きい.
<ソース:https://www.geeksforgeeks.org/heap-data-structure/minheapandmaxheap/>

これらの属性のため、hipでは、最も低い(またはそれ以上の)優先度を持つノードが常にルートノードに来るため、優先度キューなどの抽象データ型を実現するために利用することができる.
(この場合、キー値の大小関係は親/子ノード間のみで、兄弟ノード間では成立しません)

Python heapデータ構造

Python heapqモジュールは、heapq(優先キュー)アルゴリズムを提供する.

すべての親ノードの値は、その子ノードのバイナリツリー構造よりも小さいか、またはそれよりも大きい.内部はインデックス0から始まり、k個の要素は、常に子要素(2 k+1、2 k+2)よりも小さいまたは等しい最小hop形式でソートされる.

(1)関数の使用

heapq.heappush(heap,item):itemをheap

に追加

heapq.heapppop(heap):heapの最小要素をポップアップして返します.空の場合はIndexErrorが呼び出されます.

heapq.heapify(x):リストxをすぐにheapに変換します.

(2)heapを作成して要素を追加する

heapqはmin-heapのようにリストを処理できるので、空のリストを作成した後、heapqの関数を呼び出すたびにリストをパラメータに渡す必要があります.

import heapq

heap = []
heapq.heappush(heap, 40)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heap)   # [10, 40, 20]

リストが作成されている場合は、heapifyで直接heapに変更できます.

heap2 = [40, 10, 20]
heapq.heapify(heap2)

print(heap2)   # [10, 40, 20]

(3)heap要素の削除

heapppop関数は、最小要素をhipから削除し、結果値を返します.

result = heapq.heappop(heap)

print(result)   # 10
print(heapq)   # [20, 40]

heapの最小要素10は戻り、hipから除去される.
除去後もMin-Heap構造を満足

(4)Max-Heapの作成

基本的に、PythonのheapqモジュールはMin-Heapで実現されるので、Max-Heapを実現するにはいくつかのテクニックが必要です.
=>y=-x変換時、最切り上げソートは最値ソートに変換されます!
お尻にエレメントを追加する場合(-item,item)はtupleの形で入れ、tupleの最初のエレメントで優先お尻を構成しますが、エレメント値の符号が変わったため、最小お尻で実現するheapqモジュールを最大お尻に運用します.

heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
  heapq.heappush(max_heap, (-item, item))

print(max_heap)  # [(-9, 9), (-7, 7), (-3, 3), (-1, 1), (-5, 5)]

max_item = heapq.heappop(max_heap)[1]
print(max_item)   # 9

heapppopを使用すると、hip上の最大値が返されることが確認できます.このとき、実際の要素値はtupleの2番目の位置に格納されます.

リファレンス

https://docs.python.org/2/library/heapq.html
https://littlefoxdiary.tistory.com/3
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html