Python で最小ヒープを実装する
ツリーは、要素が複数のレベルに配置されている非線形データ構造です。 ヒープはツリーに基づくデータ構造です。
これは、すべての親ノードに 2つの子ノードがあることを意味する完全なバイナリ ツリーです。 ヒープはさまざまなアルゴリズムを実装し、他の構造をソートし、キューに優先順位を付けます。
ヒープには、最大と最小の 2つのタイプがあります。 これらは、親ノードと比較した子ノードの値に基づいています。
このチュートリアルでは、最小ヒープとその Python での実装について説明します。
Python の最小ヒープ
すべての親ノードは、最小ヒープ内の子ノード以下です。 昇順に従い、常に小さいノードが優先されます。
特定のノード n の場合、その左の子は 2n+1 にあり、右の子は 2n+2 にあります。
次の画像を参照してください。
Python では、最小ヒープを 2つの方法で実装できます。 これらについては以下で説明します。
Python で最小ヒープを実装するクラスを作成する
Python で Min Heap を実装するクラスを作成できます。 ヒープのサイズでクラス オブジェクトを開始し、要素の挿入プロセスを実行してそれぞれのインデックスにマップするメソッドを定義します。
例：
import sys
class min_heap:
def __init__(self, size):
self.storage = [0] * size
self.size = size
self.heap_size = 0
self.Heap = [0] * (self.size + 1)
self.Heap[0] = sys.maxsize * -1
self.parent = 1
self.root = 1
def parent_idx(self, idx):
return (idx - 1) // 2
def lf_child_idx(self, idx):
return 2 * idx + 1
def rt_child_idx(self, idx):
return 2 * idx + 2
def has_parent(self, idx):
return self.parent_idx(idx) >= 0
def insert(self, idx):
if self.heap_size >= self.size:
return
self.heap_size += 1
self.Heap[self.heap_size] = idx
heap = self.heap_size
while self.Heap[heap] < self.Heap[heap // 2]:
self.swap(heap, heap // 2)
heap = heap // 2
def swap(self, left, right):
self.Heap[left], self.Heap[right] = self.Heap[right], self.Heap[left]
def print_heap(self):
for i in range(1, (self.heap_size // 2) + 1):
print(
"Parent:",
str(self.Heap[i]),
"Lt: " + str(self.Heap[2 * i]),
"Rt: ",
str(self.Heap[2 * i + 1]),
)
min_heap = min_heap(10)
min_heap.insert(5)
min_heap.insert(1)
min_heap.insert(8)
min_heap.insert(2)
min_heap.insert(3)
min_heap.insert(7)
min_heap.insert(9)
min_heap.insert(6)
min_heap.insert(10)
min_heap.print_heap()
出力：
Parent: 1 Lt: 2 Rt: 7
Parent: 2 Lt: 5 Rt: 3
Parent: 7 Lt: 8 Rt: 9
Parent: 5 Lt: 6 Rt: 10
insert() メソッドは要素をヒープに追加します。 要素のインデックスと順序は、rt_child_index() および lt_child_index() 関数を使用して親ノードの値に基づいて子ノードのレベルを調整する swap() メソッドを使用して管理されます。
Min Heap は、クラスの print_heap() 関数を使用して反復処理され、順番に表示されます。
heapq モジュールを使用して Python で最小ヒープを実装する
Python は、他のクラスを作成せずにヒープ データ構造を実装できる heapq モジュールを提供します。 このモジュールは、最小ヒープ構造を維持するために、ヒープの最小要素が毎回ポップされるようにします。
ヒープのノードを維持するためにリストを使用します。 要素は heappush() 関数を使用して追加され、それに応じて順序が維持されるため、最小ヒープの構造が維持されます。
heappop() は、ヒープから最小の要素であるルート ノードをポップします。
例：
import heapq as heap
lst = []
heap.heappush(lst, 7)
heap.heappush(lst, 1)
heap.heappush(lst, 5)
heap.heappush(lst, 4)
heap.heappush(lst, 8)
heap.heappush(lst, 3)
print("Heap: ", lst)
print("Parent Node: ", heap.heappop(lst))
print("Child Nodes: ", lst)
出力：
Heap: [1, 4, 3, 7, 8, 5]
Parent Node: 1
Child Nodes: [3, 4, 5, 7, 8]
上記の例では、リスト lst を使用してヒープを維持しました。 要素が追加され、その順序は heappush() 関数で自動的に調整されます。
最小ヒープが表示されます。 親ノードは heappop() メソッドを使用してポップされ、表示されます。
親ノードを削除すると、残りの子ノードも表示されます。
Manav is a IT Professional who has a lot of experience as a core developer in many live projects. He is an avid learner who enjoys learning new things and sharing his findings whenever possible.
LinkedIn