HeapとPython「heapq」モジュール

📖 優先キュー

キュー(queue)は、データを先に入れるFIFO(First In First Out)構造を有する周知のデータ構造の1つである.
優先度キューは、キューとは異なり、最も優先度の高いデータが最初に現れるデータ構造です.
(Ex.物を入れる順番ではなく、高価な物の順番で取り出す必要がある場合)
これらの優先キューには、リストによって実装される方法と、スタックによって実装される方法がある.
リストによる時間的複雑度は挿入時O(1),削除時O(N),hipによる時間的複雑度は挿入,削除時平均O(logn)である.
お尻で表現するほうが効率的です

🤷だからheapは?

HIPは完全なツリーデータ構造であり、最高価格と最高価格を迅速に計算することを目的としています.
hipは親ノードと子ノードの値を比較し,より優先度の高いノードをルートノードとする.
お尻には最小のお尻(Min heap)と最大のお尻(Max heap)があります.

最小スタック(minheap)
-ルートノードの最小値->最高価格

最大ヒープ(最大ヒープ)
-ルートノードには常に大きな値があります->最低価格

最小臀部の例

📝 どのように実現しますか?

実装を容易にするために、ツリー内の最初のインデックス(0)は使用できません.
hipでは、親ノードと子ノードの関係は次のとおりです.

左サブノードのインデックス:(親ノードのインデックス)*2

右側の子ノードのインデックス:(親ノードのインデックス)*2+1

親ノードのインデックス=(子ノードのインデックス)/2

挿入時
まず、最後に値を挿入し、親ノードと値を比較して配置します.
例は以下のとおりです.

2を追加すると、最後に値が加算されます.

親ノード8よりも2が小さく、位置を変えることができます.

親ノードと再度比較し、値を変更します.
**削除**
ルートノードの値を削除し、最後のノードをルートノードにアップグレードします.

2を抜き、最下位のノード8をルートノードに昇格させる.

この状態で、最小ノードを再びルートノードに昇格させます.

この状態で、最小ノードを再びルートノードに昇格させます.

👍 pythonのheapqモジュール

Pythonはheapqモジュールを提供してこれらのhipを実現した.

import heapq

前述したようにheapqを使用することができる.
使い方は以下の通りです.

heap = []
heapq.heapify(heap) # 리스트를 힙 구조로 변환
heapq.heappush(heap, item) # 힙에다가 item을 삽입 
heapq.heappop(heap) # 힙에서 루트 노드를 pop하고 리턴 (만약 힙이 비어있는 경우에는 IndexError 호출)